Find Prime Numbers using ‘Sieve of Eratosthenes’

Introduction

Sieve of Eratosthenes

Use Sieve of Eratosthenes to find all the prime numbers in a range of running integer numbers. Sieve of Eratosthenes is one of the most efficient methods of finding prime numbers.

In Sieve of Eratosthenes derivation, given a range of running integer numbers. Each iteration one prime number is picked up and all its multiples are marked as composite numbers. After the removals, all the remaining unmarked numbers are prime numbers.

Reference: http://www.geeksforgeeks.org/sieve-of-eratosthenes/

void sieve(int N)

{

    bool isPrime[N + 1];

    for (int i = 0; i& lt; = N; ++i) {

isPrime[i] = true;

    }

isPrime[0] = false;

isPrime[1] = false;

    for (int i = 2; i * i <= N; ++i) {

        // Mark all the multiples of i as composite numbers

        if (isPrime[i] == true) {

            for (int j = i * i; j <= N; j += i)

isPrime[j] = false;

        }

    }

}

Infinite Prime Numbers Derivation

Sieve of Eratosthenes derivation find all the Prime Numbers in a fixed range of running integer number.

The program illustrated below will find all the Prime Numbers infinitely without limiting to a range and it is multithreaded.

Computer has relatively small RAM and relatively big hard disk storage. In order not to exhaust the computer RAM, we can firstly find all the Prime Numbers for a given fixed range of running integer number. Then we save the Prime Number results as a file into the hard disk. In this way we can derive our Prime Numbers infinitely as long as the hard disk still have spaces.

1. Program declares a fixed size array to hold fixed range of running number.

2. Read the previously derived Prime Number results from hard disk saved files and push them to a queue. Each time only read from a single file.

3. Set isPrimeNumber to false for all the multiples of a Prime Number from saved queue that are within the current running integer numbers range.

4. Repeat steps 2 & 3 until all the multiples of previously saved Prime Numbers are removed from the current running numbers range.

5. Run Sieve of Eratosthenes function on the current running integer number range

6. Save the current running number range’s Prime Number results into a new file in hard disk

7. Increment to the next running number range and restart the process

Visual C++

FindPrimeNumbers.cpp

Figure: Prime Numbers count from each running integer number range

From the graph, there is a trend Prime numbers count decrease when running number are getting bigger

References

· http://www.geeksforgeeks.org/sieve-of-eratosthenes/

· https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

---

Edit date: 4 June 2020