[Tutor] OverflowError: cannot fit 'long' into an index-sized integer

[Steven D'Aprano]

On Tue, Jan 07, 2014 at 01:32:51PM -0800, Danny Yoo wrote:
> Hi Keith,
> 
> Ah, good point.  I did not realize that we could use a sqrt() to get a
> good upper bound on what primes we can consider.  That cuts down on
> the size of the search space enormously.  Ok, I take my objection back
> then.
> 
> (That being said, I'm fairly certain that this problem can be solved
> in constant space, without maintaining an explicit sieve.)


If you are interested in a range of algorithms for calculating primes, 
you might like to check out this:

https://pypi.python.org/pypi/pyprimes/0.1


Some of the file is a bit clunky, with a few design decisions I'm not 
sure I would still go with today, but the basic algorithms are still 
strong. Even on my clunk old PC with 1GB of RAM, performance is 
reasonable. This is using Python 2.7:

py> import pyprimes
py> with Stopwatch():
...     pyprimes.factors(600851475143)
...
[71, 839, 1471, 6857L]
elapsed time is very small; consider using timeit.Timer for 
micro-timings of small code snippets
time taken: 0.000825 seconds


And if you want all the prime numbers:

py> with Stopwatch():
...     primes = list(pyprimes.primes_below(50000000))
...
time taken: 44.911147 seconds
py> len(primes)
3001134
py> primes[:5]
[2, 3, 5, 7, 11]
py> primes[-5:]
[49999883, 49999897, 49999903, 49999921, 49999991]


That doesn't beat any speed records, especially not on my computer, but 
I have a few ideas for speeding it up and will come back to it some day.


(The call to Stopwatch is a utility function I use to time blocks of 
code. If anyone is interested in the code, let me know.)


-- 
Steven