Sieve of Eratosthenes - Classic Problems | Repovive

CLS24. Sieve of Eratosthenes

1s256 MB

Given an integer $n$ , count how many prime numbers are less than or equal to $n$ .

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

$n$

$\text{count of primes} \le n$

Input

Explanation

For this input, the required output is 4.

Output

Input

Explanation

For this input, the required output is 25.

Output

Input

Explanation

For this input, the required output is 1.

Output

Given an integer $n$ , count how many prime numbers are less than or equal to $n$ .

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

$\text{count of primes} \le n$