Find primes – C # Tutorial

Prime numbers play an important role in modern encryption methods, which is why it is especially important in computer science to know how to find primes.

In this tutorial we want to use one of the most common algorithms to find all primes up to a defined limit. For this we use the so-called “Sieve of Eratosthenes” (see Wikipedia).

Primes are all natural numbers that are only divisible by 1 and themselves. A prime number has exactly two divisors. So any number that is a multiple of a prime number is not a prime number. The “Sieve of Eratosthenes” uses this property to delete from a list all non-prime numbers and leave only those that are prime numbers.

Procedure according to the sieve of Eratosthenes

  1. Make a list of all numbers from 2 to the limit (max)
  2. The smallest unmarked number is a prime number (–> in the first step the 2)
  3. Mark all multiples of this number in the list as “no prime”
  4. Repeat steps 2 and 3 until the square of the found prime number is greater than the limit.

Example – Prime numbers until 20:

Step 1:
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20

Step 2.1 (Primes are red):
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20

Step 3.1 (Multiples are green):
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20

Step 2.2 (3 is a prime number):
234 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20

Step 3.2 (mark all multiples of 3):
234 – 5 – 6 – 7 – 8910 – 11 – 12 – 13 – 141516 – 17 – 18 – 19 – 20

Step 2.3 (The next unmarked number is the 5):
23456 – 7 – 8910 – 11 – 12 – 13 – 141516 – 17 – 18 – 19 – 20

Step 3.3 (all multiples of 5 are already marked):
23456 – 7 – 8910 – 11 – 12 – 13 – 141516 – 17 – 18 – 19 – 20

We do not need further steps as the next unmarked number in the list is 7 and 7 * 7 = 49 and 49> 20.

Consequently, all remaining numbers in our list are primes:
234567891011121314151617181920

To implement this algorithm exactly as in the example in C#, we first create a function named findPrimes, which takes as parameter our limit (max) and returns a list of primes as List<int>:

The function is static, because it is called from the main function in our simple console application.

In our function we first need two variables, more precisely a list in which we later store the found primes, and an array with all numbers from 0 to the limit (max). The array is of type bool, where true is prime and false is not prime.

Before we continue, we check the limit given as a parameter (max), because if this is less than two, we need not do any further operations. In that case there are no primes and we return the previously initialized empty list primes.

Next we set all values in numbers to true. This means that all numbers are primarily marked as prime numbers and we will mark all multiples of the prime numbers as no prime number (false) in the further steps.

Now declare a new variable and set it to the first prime number (2). We call this variable p, which stands for the current prime or position.

Then loop the steps 2 and 3 (explained at the beginning) until the square of the current prime number is greater than the limit.

In the loop, we use a For-loop to go through all multiples of the prime number p and mark them false (= no prime). We start with p + p, since p itself is still a prime number and should not be marked as false.

In the second part of the while-loop we go through the array until we get to the next number marked as prime or to the next number that is not marked as multiple. This number automatically becomes a prime number. The process is then repeated until the condition for the while-loop is no longer satisfied.

Then we have to find all numbers marked as prime numbers in the array and add them to our primes declared at the beginning:

Don’t forget to return the list of primes:

 

The whole code

In the following we see the complete uncommented code that is compilable and executable. The program finds all primes up to 1000 and outputs them in the console.

The output looks like this:

2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503; 509; 521; 523; 541; 547; 557; 563; 569; 571; 577; 587; 593; 599; 601; 607; 613; 617; 619; 631; 641; 643; 647; 653; 659; 661; 673; 677; 683; 691; 701; 709; 719; 727; 733; 739; 743; 751; 757; 761; 769; 773; 787; 797; 809; 811; 821; 823; 827; 829; 839; 853; 857; 859; 863; 877; 881; 883; 887; 907; 911; 919; 929; 937; 941; 947; 953; 967; 971; 977; 983; 991; 997;

 


 

Epilogue

This algorithm is very easy to implement, but requires a certain amount of computation time to execute so many loops. The code can be optimized, for example, by initializing the array at the beginning already all even numbers are set to false. This saves the first and longest loop in calculating the multiples. Sure, there is one or the other trick to further improve the performance and to reduce the memory usage, but this should not be in this tutorial.

2 replies on “Find primes – C # Tutorial”

  1. Great tutorial! This really helped me, please continue this kind of tutorials, can i share it?

  2. why there is one or the other trick to further improve the performance and to reduce the memory usage?

Leave a Reply

Your email address will not be published. Required fields are marked *