OFFSET
2,5
COMMENTS
Equivalent to removing all multiples of numbers from 2 to smallest divisor of n from the set [2..n].
There should be a simple formula. - N. J. A. Sloane, May 29 2022
LINKS
Rémy Sigrist, Table of n, a(n) for n = 2..10000
Wikipedia, Sieve of Eratosthenes
FORMULA
a(2*n) = n - 1 for any n > 0. - Rémy Sigrist, Jun 02 2022
EXAMPLE
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.
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Nicola Pesenti, Apr 07 2022
STATUS
approved