A055399 Number of stages of sieve of Eratosthenes needed to identify n as prime or composite.

1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 4, 1, 4, 1, 2, 1, 3, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 5, 1, 3, 1, 2, 1, 5, 1, 5, 1, 2, 1, 3, 1, 5, 1, 2, 1, 5, 1, 5, 1, 2, 1, 4, 1, 5, 1, 2, 1, 5, 1, 3, 1, 2, 1, 5

Offset

3,3

Comments

Primes are known as primes actually one step before a(n): at step k of the sieve, multiples of prime(k) are removed, the smallest integer removed being prime(k)^2; every remaining integer less than prime(k+1)^2 will then never be removed, and it is newly known at step k for those between prime(k)^2 and prime(k+1)^2. For example, at step 3, multiples of prime(3) = 5 are removed and remaining integers after this step are prime up to prime(4)^2 = 49; then, 29, 31, 37, 41, 43, 47 are known as prime at step 3. - Jean-Christophe Hervé, Nov 01 2013

Links

T. D. Noe, Table of n, a(n) for n = 3..10000

H. B. Meyer, Eratosthenes' sieve

J. Britton, Sieve of Eratosthenes Applet

C. K. Caldwell, The Prime Glossary, Sieve of Eratosthenes

Wikipedia, Sieve of Eratosthenes

Formula

If n is composite, a(n) = A055396(n); if n is prime, a(n) = pi(firstprimeabove(sqrt(n)). [Corrected by Charles R Greathouse IV, Sep 03 2013]

a(n) = A010051(n)*(A056811(n)+1)+(1-A010051(n))*A055396(n). - Jean-Christophe Hervé, Nov 01 2013

Example

a(7)=2 because 7 is not removed by the first two stages of the sieve, but is less than the square of the second prime (though not the square of the first); a(35)=3 because 35 is removed in the third stage as a multiple of 5.

Mathematica

a[n_ /; !PrimeQ[n]] := PrimePi[ FactorInteger[n][[1, 1]]]; a[n_ /; PrimeQ[n]] := PrimePi[ NextPrime[ Sqrt[n]]]; Table[a[n], {n, 3, 107}](* Jean-François Alcover, Jun 11 2012, after formula *)

Crossrefs

Cf. A000040, A002808, A004280, A038179, A055396, A054403, A055398, A083269, A010051, A056811.

Sequence in context: A060775 A355368 A175494 * A029426 A369916 A085342

Adjacent sequences: A055396 A055397 A055398 * A055400 A055401 A055402

Keyword

nice,nonn,easy

Author

Henry Bottomley, May 15 2000

Status

approved