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 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
