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 2n-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

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:

Natural Number 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.
All of the prime numbers between 1 and 100.

The prime numbers between 1 and 1,000 are:

  • There are in total of 168 prime numbers between 1 to 1000.
23571113171923
293137414347535961
67717379838997101103
107109113127131137139149151
157163167173179181191193197
199211223227229233239241251
257263269271277281283293307
311313317331337347349353359
367373379383389397401409419
421431433439443449457461463
467479487491499503509521523
541547557563569571577587593
599601607613617619631641643
647653659661673677683691701
709719727733739743751757761
769773787797809811821823827
829839853857859863877881883
887907911919929937941947953
967971977983991997
Prime numbers between 1 and 1,000

Largest Prime Number

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