Math Number Theory Combinatorics
Intermediate Level

Implement the sievePrimeCount method that counts prime numbers up to n using sieve-style marking.

The input contains an integer n. Your task is to count how many prime numbers exist from 2 up to n.

A prime number has exactly two positive divisors: 1 and itself. For example, up to 20, the prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, so the answer is 8.

Example 1
Input:
n (int) = 20
Return:
(int) 8
Example 2
Input:
n (int) = 10
Return:
(int) 4
Example 3
Input:
n (int) = 1
Return:
(int) 0

Use the Sieve of Eratosthenes to mark non-prime numbers efficiently.

Start by assuming every number from 2 to n is prime. For each prime candidate, mark all of its multiples as non-prime.

After marking is complete, count the values that are still marked as prime.

Pseudocode:

function sievePrimeCount(n):
    if n < 2:
        return 0
    isPrime = array of n + 1 values filled with true
    isPrime[0] = false
    isPrime[1] = false
    p = 2
    while p * p <= n:
        if isPrime[p] == true:
            for multiple from p * p to n step p:
                isPrime[multiple] = false
        p++
    count = 0
    for i from 2 to n:
        if isPrime[i] == true:
            count++
    return count
Run your code to see the result.