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 overall decreasing when running number are getting bigger. Prime Number counts slightly fluctuating in each running integer number ranges.

 

 

Total count of Prime Number

 

Count of Prime Numbers (between 1~210000000) Residue Class Mod 2

0

1

1

11601625

Count of Prime Numbers (between 1~210000000) Residue Class Mod 3

0

1

1

5800349

2

5801276

Count of Prime Numbers (between 1~210000000) Residue Class Mod 4

2 & 4 are not coprime

1

5800088

2

1

3

5801537

Count of Prime Numbers (between 1~210000000) Residue Class Mod 5

0

1

1

2900345

2

2900737

3

2900514

4

2900029

Count of Prime Numbers (between 1~210000000) Residue Class Mod 6

2, 3 & 6 are not coprime

1

5800349

2

1

3

1

5

5801275

Count of Prime Numbers (between 1~210000000) Residue Class Mod 7

0

1

1

1933664

2

1933548

3

1933719

4

1933407

5

1933723

6

1933564

Count of Prime Numbers (between 1~210000000) Residue Class Mod 8

1

2899570

2

1

3

2900901

5

2900518

7

2900636

Count of Prime Numbers (between 1~210000000) Residue Class Mod 9

1

1933285

2

1933861

3

1

4

1933414

5

1933739

7

1933650

8

1933676

Count of Prime Numbers (between 1~210000000) Residue Class Mod 10

1

2900345

2

1

3

2900514

5

1

7

2900736

9

2900029

Count of Prime Numbers (between 1~210000000) Residue Class Mod 11

0

1

1

1160183

2

1160218

3

1159950

4

1160020

5

1160161

6

1160317

7

1160117

8

1160477

9

1160296

10

1159886

Count of Prime Numbers (between 1~210000000) Residue Class Mod 12

1

2899639

2

1

3

1

5

2900449

7

2900710

11

2900826

 

Observing from the above Prime Number Residue Class Mod N tables, prime number apparently roughly evenly distributed among the Residue Class Mod N.

 

 

 

 

References

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Edit date: 4 June 2020