Re:Prime number patterns
by thomasahle on Tuesday November 11, 2014 @01:52PM
(#8591475)
I like this way of using numpy. This resembles the sieve of eratosthenes, so you'd think it was fast.
However `n%p[-1]` isn't fast to do, your inner loop ends up taking nearly linear time. At least linear in the final number of primes, which is larger than `N/logN`. Hence your algorithm runs in `N^(3/2)` whereas eratosthenes is `NloglogN`.
Funny how many versions of this algorithm there are out there.
I noticed it ran a bit slow... it is supposed to be Eratosthenes Sieve
Re:Prime number patterns
by christophilus on Tuesday November 11, 2014 @01:35PM
(#8591371)
Hm. I should credit the source... Will put that on my todo list tonight. I transformed these into JSON: https://primes.utm.edu/lists/small/millions/
Re:Prime number patterns
by christophilus on Tuesday November 11, 2014 @01:37PM
(#8591387)
Yeah. I thought about shrinking the dataset down to 10k primes instead of 1m primes, as the patterns would still hold up, but the load/rendering times would greatly improve.
I found them: https://primes.utm.edu/lists/small/millions/ He says: Usually it is faster to run a program on your own computer than to download them.
Here in numpy: