A353283 Minimum number of numbers to drop to determine whether n is a prime number using the Sieve of Eratosthenes algorithm.
0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 8, 7, 9, 8, 10, 9, 12, 10, 13, 11, 15, 12, 16, 13, 18, 14, 19, 15, 20, 16, 23, 17, 24, 18, 24, 19, 27, 20, 28, 21, 28, 22, 31, 23, 33, 24, 32, 25, 36, 26, 37, 27, 36, 28, 41, 29, 42, 30, 40, 31, 45, 32, 47, 33, 44, 34, 50, 35, 51, 36, 48
Offset: 2
Keywords
Examples
a(15) = 8 because: First pass: drop multiples of 2: 2 3 x 5 x 7 x 9 x 11 x 13 x 15 Second pass: drop multiples of 3: 2 3 _ 5 _ 7 _ x _ 11 _ 13 _ x 15 was dropped so it is not prime; 8 numbers were dropped.
Links
- Rémy Sigrist, Table of n, a(n) for n = 2..10000
- Wikipedia, Sieve of Eratosthenes
Programs
-
Haskell
f n=n-2-r[2..n] where r(h:t)|n`elem`t=1+r[x|x<- t,x`mod`h>0] |1>0=length t -
PARI
for (n=2, #b=apply (k->if (k==1, 0, primepi(divisors(k)[2])), [1..75]), print1 (sum(k=2, n, b[k]<=b[n])-b[n]", ")) \\ Rémy Sigrist, Jun 02 2022
Formula
a(2*n) = n - 1 for any n > 0. - Rémy Sigrist, Jun 02 2022
Comments