Prime number determination (aka Sieve of Eratosthenes)

#codingtest #csharp

Prime number determination can be approached in several ways.

Basic Double For-Loop

bool[] era = new bool[1000001]; // 1,000,000

// 0 & 1 are not prime numbers
era[0] = true;
era[1] = true;

for(int i = 2; i <= era.Length; i++)
{
    for(int j = 2; j <= i; j++)
    {
        if(i % j == 0)
        {
            era[i] = true;
            break;
        }
    }
}

In this way, it is fundamentally possible to determine primes using a double for-loop.

However, this method has a time complexity of up to

O(n^2)

, making it highly inefficient.

In practice, with 1,000,000 data points, it takes more than 10 seconds to execute.

For-Loop Using Square Root

Let's think simply about what makes a number prime.

Take the number 10.
The square root of 10 is about 3.xxxxx.
If there is any number between 2 and 3 that divides 10 evenly, then 10 is not a prime.

For example, for 121:
If any number between 2 and 11 divides 121 evenly, then 121 is not a prime.
Since 121 % 11 == 0, it is not a prime.

The code looks like this:

bool[] era = new bool[1000001]; // 1,000,000

// 0 & 1 are not prime numbers
era[0] = true;
era[1] = true;

for(int i = 2; i <= era.Length; i++)
{
    int sqrt = (int)Math.Sqrt(i);
    for(int j = 2; j <= sqrt; j++)
    {
        if(i % j == 0)
        {
            era[i] = true;
            break;
        }
    }
}

This method is sufficiently fast, but there is an even faster approach.

The time complexity is

O(n * \sqrt{n})

Sieve of Eratosthenes

This method starts from 2 and eliminates all multiples of each number except itself, leaving only prime numbers.

For example, starting from 2, you eliminate 4, 6, 8, etc. (all multiples of 2 except 2 itself).
Then, for 3, you eliminate 6, 9, 12, etc., and so on.

bool[] era = new bool[1000000]; // 1,000,000

// 0 & 1 are not prime numbers
era[0] = true;
era[1] = true;

int sqrt = (int)Math.Sqrt(era.Length);  

// 1
for (int i = 2; i <= sqrt; i++)  
{  
    // 2
    if (era[i] == false) {  
        // 2-1
        for (int j = i * i; j < era.Length; j += i)  
        {  
            era[j] = true;  
        }  
    }  
}

The process is as follows:

Since the maximum number is one million, iterate only up to the square root of one million, which is 1,000.

Even with this, all numbers up to one million are checked.

If a number has not been filtered out,

Eliminate all multiples of that number, starting from its square.

In this way, initially, 4, 6, 8, 10... are filtered, then 3, 9, 15..., and so on.
If a number has already been filtered, it is skipped, and the process continues with the next.

The time complexity is