Sieve

What is Sieve

In number theory, there are always some requests getting some special numbers, such as prime. The Sieve is the algorithm getting these numbers and the Euler Sieve is to get prime in a range and even the minimum prime factor of a number.

The Prerequisite

• Prime number: A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself.
• Composite number: A composite number is a positive integer greater than 1 that is not a prime number.
• A theorem: Every composite can be expressed as the product of its smallet prime factor and a number. It ensure that the Euler Sieve won’t miss any prime number or composite number.

The c++ code of getting prime number

void EulerSieve(int n, vector<bool>& isPrime, vector<int>& prime)
{
    isPrime.assign(n + 1, true);
    prime.clear();
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i <= n; ++i)
    {
        if(isPrime[i]) prime.push_back(i);
        for(int j = 0; j < prime.size() && i * prime[j] <= n; ++j)
        {
            isPrime[i * prime[j]] = false;
            if(i % prime[j] == 0) break;   
        }

    }
}

The function of if(i % prime[j] == 0) break;

If i % prime[j] = 0, means there exists a k such that i = k ✖️ prime[j]. If we don’t break, then x = i ✖️ prime[j + t] = k ✖️ prime[j] ✖️ prime[j + t], which means x’s smallest prime factor is prime[j] instead of prime[j + t]. Through the thereom, we will mark the same prime numbers more than 1 time. (If we don’t use it, the sieve will be Eratosthenes Sieve)

The c++ code of getting the smallest prime factor

void minPrimeFactorSieve(int n, vector<int>& minPrimeFactor, vector<int>& prime)
{
    minPrimeFactor.assign(n + 1, 0);
    prime.clear();
    minPrimeFactor[0] = minPrimeFactor[1] = INT_MAX;
    for(int i = 2; i <= n; ++i)
    {
        if(minPrimeFactor[i] == 0)
        {
            minPrimeFactor[i] = i;
            prime.push_back(i);
        }
        for(int j = 0; j < prime.size() && i * prime[j] < n>; ++j)
        {
           minPrimeFactor[i * prime[j]] = prime[j];
           if(i % prime[j] == 0) break;
        }
    } 
}