Medium · nested loops

Count the Primes

How many primes are there up to n? The first problem where the inner loop is the whole point — and where break is performance, not style.

Problem

Input: one integer n (0 ≤ n ≤ 10⁶).

Output: the count of prime numbers p with p ≤ n.

Sample:

Input	Output
`10`	`4`
`100`	`25`

Your solution

Program.cs — your solution

Custom input for "Run my input"

Judging runs entirely in your browser against hidden tests. Your code is saved locally as you type. Ctrl+Enter judges.

Stuck? Hints

Hint 1 — reuse Prime Check

The inner test is exactly the Prime Check problem: trial division up to √i, with break on the first divisor. Wrap it in a loop over 2..n and count the survivors.

Hint 2 — why the break matters

Without break you test every divisor of every number. With it, most numbers exit after one or two divisions. At n = 10⁶ that is the difference between seconds and a timeout.

Solution (try first!)

int n = int.Parse(Console.ReadLine());
int count = 0;
for (int i = 2; i <= n; i++)
{
    bool prime = true;
    for (int d = 2; d * d <= i; d++)
    {
        if (i % d == 0) { prime = false; break; }
    }
    if (prime) count++;
}
Console.WriteLine(count);

The next step up is the Sieve of Eratosthenes — a boolean array instead of trial division, turning O(n√n) into O(n log log n). Next: Armstrong Number.