Practice › Basics
Count Primes up to N
Medium · Basics · Asked at Amazon, Microsoft, Infosys
Print how many prime numbers are ≤ n.
Input
One integer n.
Output
The count of primes ≤ n.
Constraints
- 0 ≤ n ≤ 10^6
Use the Sieve of Eratosthenes.
Example 1
Input
10
Output
4
Example 2
Input
1
Output
0
Hints
- Checking every number separately is O(n√n) — too slow for 10^6.
- Sieve of Eratosthenes: for every prime p, mark p², p² + p, … as composite.
Approach
Make a boolean array isPrime[0..n], all true except 0 and 1. For each p with p * p <= n that is still marked prime, cross out its multiples starting at p² (smaller multiples were already crossed out by smaller primes). Count what stays true. Handle n < 2, where the answer is 0.
Complexity: O(n log log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n < 2) { cout << 0 << "\n"; return 0; }
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (long long p = 2; p * p <= n; p++)
if (isPrime[p])
for (long long q = p * p; q <= n; q += p) isPrime[q] = false;
cout << count(isPrime.begin(), isPrime.end(), true) << "\n";
return 0;
}Python solution
n = int(input())
if n < 2:
print(0)
else:
is_prime = bytearray([1]) * (n + 1)
is_prime[0] = is_prime[1] = 0
p = 2
while p * p <= n:
if is_prime[p]:
is_prime[p * p :: p] = bytearray(len(range(p * p, n + 1, p)))
p += 1
print(sum(is_prime))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n < 2) { System.out.println(0); return; }
boolean[] composite = new boolean[n + 1];
int count = 0;
for (int p = 2; p <= n; p++) {
if (composite[p]) continue;
count++;
for (long q = (long) p * p; q <= n; q += p) composite[(int) q] = true;
}
System.out.println(count);
}
}