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) =
20Returns (int)
8Example 2
Input
n (int) =
10Returns (int)
4Example 3
Input
n (int) =
1Returns (int)
0Use 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 countReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run