Mediummathsievearrays
Count Primes
Time limit 2 s · Memory 64 MB
Statement
You are given an integer n. Print how many prime numbers lie between 1 and n inclusive.
Constraints
1 ≤ n ≤ 10^6
Examples
Input 1
10
Output 1
4
Input 2
1
Output 2
0
Time limit 2 s · Memory 64 MB
You are given an integer n. Print how many prime numbers lie between 1 and n inclusive.
1 ≤ n ≤ 10^6
10
4
1
0