C++ and Java Code for Sieve of Eratosthenes

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthenes method:

When the algorithm terminates, all the numbers in the list that are not marked are prime.

Firstly write all the numbers from 2,3,4…. n
Now take the first prime number and mark all its multiples as visited.
Now when you move forward take another number which is unvisited yet and then follow the same step-2 with that number.
All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.

C++ Implementation

void SieveOfEratosthenes(int n)
{
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));

    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            cout << p << " ";
}

Java Implementation

class SieveOfEratosthenes {
    void sieveOfEratosthenes(int n)
    {
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++){
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }

        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
                System.out.print(i + " ");
        }
    }
}

Time complexity of Sieve of Eratosthenes :
o(n * (log(log(n)))).

Space complexity: O(1)
Source - InterviewBit

Blog

C++ and Java Code for Sieve of Eratosthenes

Kamal Sharma

C++ Implementation

Java Implementation

Join Our Newsletter. No Spam, Only the good stuff.

Related