Problem 63 - Arent you guys pushing a bit too far?
Back to General discussions forum
Guys I have tried solving the integer factorization problem in Python using a Erasthothenes sieve and have multiple times run into memory errors. Are you sure 13 digits numbers are not a bit too far for the common user's computer? Wikipedia says that there's not efficient algorithm to solve the problem
Just a thought and would like your perceptions.
Never mind, I was just browsing the forum and found something related here: http://www.codeabbey.com/index/forum_topic/e72646a244137fa4838db7abbaaee87b
An user suggest a certain upper bound for prime generation, I modified the algorithm to take that into account and it worked in 2 seconds.
@MPadilla, but why are you searching primes, instead of just factorizing the number, please refer to this page https://en.wikipedia.org/wiki/Integerfactorization#Factoringalgorithms
I had a similar problem recently and what seemed to solve memory issues for me was using a generator expression for the sieve (in Python).