What is a prime number, and how to generate prime numbers using C# programming

What is a prime number?

Who discovered prime numbers?

The concept of prime numbers, is a basic mathematical rule.

In 200 B.C., Eratosthenes created an algorithm that calculated prime numbers, known as the Sieve of Eratosthenes. Eratosthenes was an ancient Greek astronomer, geographer, and mathematician. He lived from 276 to 194 B.C. Eratosthenes is most famous for making the first accurate measurement of the circumference of the Earth. He lived and worked for most of his life in the city of Alexandria in Egypt.

History of prime numbers

Prime numbers have been studied for thousands of years. Euclid’s “Elements,” published about 300 B.C., proved several results about prime numbers. In Book 9 of the “Elements,” Euclid writes that there are infinitely many prime numbers. Euclid also provides proof of the Fundamental Theorem of Arithmetic — every integer can be written as a product of primes in a unique way. In “Elements,” Euclid solves the problem of how to create a perfect number, which is a positive integer equal to the sum of its positive divisors, using Mersenne primes. A Mersenne prime is a prime number that can be calculated with the equation 2ⁿ-1.

In 200 B.C., Eratosthenes created an algorithm that calculated prime numbers, known as the Sieve of Eratosthenes. This algorithm is one of the earliest algorithms ever written. Eratosthenes put numbers in a grid and then crossed out all multiples of numbers until the square root of the largest number in the grid is crossed out. For example, with a grid of 1 to 100, you would cross out the multiples of 2, 3, 4, 5, 6, 7, 8, 9, and 10, since 10 is the square root of 100. Since 6, 8, 9, and 10 are multiples of other numbers, you no longer need to worry about those multiples. So for this chart, you would cross out the multiples of 2, 3, 5, and 7. With these multiples crossed out, the only numbers that remain and are not crossed out are prime. This sieve enables someone to come up with large quantities of prime numbers.

But during the Dark Ages, when intellect and science were suppressed, no further work was done with prime numbers. In the 17th century, mathematicians like Fermat, Euler, and Gauss began to examine the patterns that exist within prime numbers. The conjectures and theories put out by mathematicians at the time revolutionized math, and some have yet to be proven to this day. In fact, proof of the Riemann Hypothesis, based on Bernhard Riemann’s theory about patterns in prime numbers, carries a $1 million prize from the Clay Mathematics Institute.

[Reference: https://www.livescience.com/34526-prime-numbers.html]

Definition of prime numbers

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 7 is a prime number because the only ways of writing it as a product, 1 × 7 or 7 × 1, which involves 7 itself.

Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

Short Definition: Prime numbers are positive integers which have only two factors, 1 and the integer itself. 

How can we find prime numbers in a traditional way

Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. 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 on

Example of sieve of Eratosthenes Algorithm

To find all the prime numbers less than or equal to 30, proceed as follows.

First, generate a list of integers from 2 to 30:

The first number in the list is 2; cross out every 2nd number in the list after 2 by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):

The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):

The next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after 5 by counting up from 5 in increments of 5 (i.e. all the multiples of 5):

The next number not yet crossed out in the list after 5 is 7. The next step would be to cross out every 7th number in the list after 7, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. The numbers not crossed out at this point in the list are all the prime numbers below 30:

[Reference: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes]

Prime Number Chart

• There are total of 25 prime numbers between 1 to 100.

The prime numbers between 1 and 1,000 are:

• There are in total of 168 prime numbers between 1 to 1000.

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

Largest Prime Number

• The largest prime number discovered so far is 2 raised to the 57,885,161st power minus 1, or 2^57,885,161 – 1. It is 17,425,170 digits long. It was discovered by the University of Central Missouri mathematician Curtis Cooper as part of a giant network of volunteer computers devoted to finding primes.
• It includes
  • Teams: 1,394
  • TFLOP/s: 1,250.146
  • CPUs: 2,061,292
• [Reference: https://www.mersenne.org/]

Smallest Prime Number

• Number 2 is the smallest prime number. It is only divided by 1 or itself.

Fact: 0 and 1 are not considered prime numbers.

Fact: 2 is the only even prime number.

Real-World applications of prime numbers

Computer Science

• The RSA encryption system (Cryptography): All arithmetic is done modulo nn, with n=pqn=pq and p,qp,q large primes. Decryption in this system relies on computing Euler’s phi function, φ(n)φ(n), which is hard to compute (hence the system is hard to break) unless you know the prime factorization of nn (which is also hard to calculate unless you know it upfront). Hence you need a method to generate primes (the Miller-Rabin primality checking algorithm is usually used here) and then you construct nn by multiplying the primes you have found.

Biology

• The evolutionary strategy used by cicadas of the genus Magicicada makes use of prime numbers. These insects spend most of their lives as grubs underground. They only pupate and then emerge from their burrows after 7, 13, or 17 years, at which point they fly about, breed, and then die after a few weeks at most. Biologists theorize that these prime-numbered breeding cycle lengths have evolved in order to prevent predators from synchronizing with these cycles.

https://www.youtube.com/watch?v=ivQaJwFRowc

Arts and literature

• The French composer Olivier Messiaen used prime numbers to create ametrical music through “natural phenomena”. In works such as La Nativité du Seigneur (1935) and Quatre études de rythme (1949–50), he simultaneously employs motifs with lengths given by different prime numbers to create unpredictable rhythms: the primes 41, 43, 47 and 53 appear in the third étude, “Neumes rythmiques”. According to Messiaen this way of composing was “inspired by the movements of nature, movements of free and unequal durations”.

[Reference : https://en.wikipedia.org/wiki/Prime_number]

How to find Prime numbers using C# programming

Prime Numbers – Code Structure

• Create a C# Console App project.
• Create a Class file with the name “Program”.
• Remove extra namespaces from the header.
• So we have basic code in a class as below.

• Read a number from the console and store it in the number variable.

• Create an integer variable k for counting purpose.

• Now create a for loop which starts from i (i=1) to a given number(number) .

• Now add an if condition inside the for loop to check the modulus of the value of the ‘number’ variable by the value of the ‘i’ variable is equal to 0 or not.
• If the modulus is 0 then increase the value of the k variable.

Rule: Prime numbers are always dividing by 1 and itself only.

Logic: Compute the modulus of the value of the “Given Number” by each number. If it equals 0 then it is a prime number.

• Now check the condition that k==2 means a remainder k increments only twice if the number is prime i.e., with one and the number itself.
• If k is equal to 2 means, it has two factors one and itself, so it is a prime number.
• If k does not equal to 2 means, it is more than two factors, so it is not a prime number.

Final C# script of Prime Number

Code Output

Summary

• In this article, we learned about prime numbers, how prime number connected with real-world and how we can find prime numbers using the C# programming language