OFFSET

1,2

COMMENTS

A well-known application of the principle of inclusion-exclusion used in sieve methods.

Number of numbers less than or equal to n and coprime to the product of the primes less than sqrt(n), i.e., to A104588(n). - Lekraj Beedassy, Mar 17 2005

LINKS

G. C. Greubel, Table of n, a(n) for n = 1..1000

FORMULA

a(n) = Sum_{k=1..n} mu(k)*floor(n/k) where each prime factor of k is <= sqrt(n). [Corrected by Steven Foster Clark, May 03 2023]

MATHEMATICA

Table[PrimePi[n] - PrimePi[Sqrt[n]] + 1, {n, 1, 100}] (* G. C. Greubel, May 13 2017 *)

PROG

(PARI) for(n=1, 100, print1(primepi(n) - primepi(sqrt(n)) + 1, ", ")) \\ G. C. Greubel, May 13 2017

CROSSREFS

KEYWORD

nonn

AUTHOR

Benoit Cloitre, Feb 16 2003

EXTENSIONS

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 12 2007

STATUS

approved