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

Author

Henry Bottomley, May 15 2000

Keywords

• nice
• nonn
• easy

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

Examples

			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.
		

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

Crossrefs

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

Programs

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 *)

Formula

If n is composite, a(n) = A055396(n); if n is prime, a(n) = A056811(n)+1. [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