Medium · sieve

Count the Primes

Read N and count how many primes are ≤ N. Trial division fits (you did one number in Prime Check) — but for N = 10,000, the Sieve of Eratosthenes is the difference between instant and sluggish, and it's your first classic algorithm-as-data-structure.

At a glanceSieve of Eratosthenes — mark every multiple of each prime up to N, then count what is still unmarked; the answer for N = 10 is 4 (2, 3, 5, 7).

Problem

Input: one integer N (1 ≤ N ≤ 10,000).

Output: how many primes p satisfy 2 ≤ p ≤ N.

Samples:

Input	Output	Why
`10`	`4`	2, 3, 5, 7
`1`	`0`	1 is not prime

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — the sieve idea

Make bool is[10001], set everything to true, then is[1] = false. Walk i from 2 up: if is[i] is still true, i is prime — count it, and cross out all its multiples (j = i*i, i*i+i, …). Whatever survives to the end is prime.

Hint 2 — two classic refinements

Start crossing at i * i, not 2 * i: smaller multiples were already crossed by smaller primes (6 was killed by 2 before 3 gets there). And you can stop the outer walk at i * i <= n — every composite ≤ n has a factor ≤ √n (the same fact from Prime Check). Counting can then be a separate loop, or a running counter.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool is[10001];
    for (int i = 0; i <= n; i++) is[i] = true;
    is[1] = false;
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (is[i]) {
            count++;
            for (int j = i * i; j <= n; j += i) is[j] = false;
        }
    }
    cout << count << endl;
    return 0;
}

Fun check: π(10,000) = 1,229 — the judge's biggest test. The sieve is ~N·log·log N work versus trial division's roughly N·√N: for N = 10,000 that's ~30,000 steps vs ~1,000,000. That gap — and the array of booleans that buys it — is the whole idea behind trading memory for speed, which is half of algorithm design. The other half is in Euclid's algorithm.

Deep dive

Why this works

The sieve trades memory for time: mark multiples instead of testing every number, and O(n√n) collapses to O(n log log n).

The cost

O(n log log n) time, O(n) space. 10,000 numbers take a few thousand operations instead of a million.

Where it goes wrong

Starting the inner loop at 2*i instead of i*i is correct but does redundant work — every composite gets marked several times.
An int array of 10^6 on the stack is 4 MB, near typical stack limits. Keep sizes modest in this browser engine.

Next step

Another algorithm older than your language: GCD.

Two things to remember

Sieve: mark multiples, never test each number.
Memory for time is the first real engineering trade-off.

🐞 This version fails — open it and try

Forgets is[1] = false, so 1 gets counted

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool is[10001];
    for (int i = 0; i <= n; i++) is[i] = true;
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (is[i]) {
            count++;
            for (int j = i * i; j <= n; j += i) is[j] = false;
        }
    }
    cout << count << endl;
    return 0;
}