Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Use the Sieve of Eratosthenes.

Example 1

Input

10

Output

4

Example 2

Input

1

Output

0

Hints

  1. Checking every number separately is O(n√n) — too slow for 10^6.
  2. 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);
    }
}

Solve Count Primes up to N online · All practice problems