Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #32 Aug 14 2024 08:35:26
%S 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,
%T 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,
%U 5,1,5,1,2,1,4,1,5,1,2,1,5,1,3,1,2,1,5
%N Number of stages of sieve of Eratosthenes needed to identify n as prime or composite.
%C 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
%H T. D. Noe, <a href="/A055399/b055399.txt">Table of n, a(n) for n = 3..10000</a>
%H H. B. Meyer, <a href="http://www.hbmeyer.de/eratosiv.htm">Eratosthenes' sieve</a>
%H J. Britton, <a href="https://web.archive.org/web/20170617094228/http://britton.disted.camosun.bc.ca/jberatosthenes.htm">Sieve of Eratosthenes Applet</a>
%H C. K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php/SieveOfEratosthenes.html">Sieve of Eratosthenes</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a>
%F 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]
%F a(n) = A010051(n)*(A056811(n)+1)+(1-A010051(n))*A055396(n). - _Jean-Christophe Hervé_, Nov 01 2013
%e 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.
%t 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 *)
%Y Cf. A000040, A002808, A004280, A038179, A055396, A054403, A055398, A083269, A010051, A056811.
%K nice,nonn,easy
%O 3,3
%A _Henry Bottomley_, May 15 2000