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.
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.