Show HN: Super fast continuous prime sieve

#1

Post by ghostforceone » Sun, Mar 05, 2023, 6:57 PM UTC

Show HN: Super fast continuous prime sieve
cocalc.com

Re: Show HN: Super fast continuous prime sieve

#2

Post by eesmith » Sun, Mar 05, 2023, 8:25 PM UTC

It uses SageMath. Replace ".nbits()" with ".bit_length()" for normal Python (documentation says nbits is an alias: https://doc.sagemath.org/html/en/reference/rings_standard/sa... ).

You'll also need to remove the IPython import if not using a notebook.

Curiously, the listed output includes:

   First 5 primes found and last five primes found [2, 3, 11, 13, 17] 
     ... [4194295, 4194299, 4194301, 4194305, 4194307]

5 and 7 are not on that list. And 4194295 = 5 * 7 * 293 * 409 is not prime, and 4194299 = 29 * 61 * 2371 is also not prime. And 4194305 is clearly not prime either.

How is this supposed to be a prime sieve?

Re: Show HN: Super fast continuous prime sieve

#3

Post by yarg » Tue, Mar 07, 2023, 11:38 AM UTC

eesmith wrote: post #2

It uses SageMath. Replace ".nbits()" with ".bit_length()" for normal Python (documentation says nbits is an alias: https://doc.sagemath.org/html/en/reference/rings_standard/sa... ). You'll also need to remove the IPython import if not using a notebook. Curiously, the listed output includes: First 5 primes found and last five primes found [2, 3, 11, 13, 17] ... [4194295, 4194299, 4194301, 4194305, 4194307] 5 and 7 are…

It isn't, at all.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

There's quite a cool GIF on the wikipedia page that shows the actual (fixed size) algorithm.

I was hoping that this would be an expanding generalisation of that, but it really isn't.