News for hackers. Stuff that matters.
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.

Re:Prime number patterns by mrcactu5 on Wednesday November 12, 2014 @08:00AM (#8595226)
I noticed it ran a bit slow... it is supposed to be Eratosthenes Sieve