The fastest way to find a prime number

The fastest way to find a prime number:

Before going into the details of the algorithm to check a number is prime or composite, we state the definition of a prime number and composite numbers.

Prime Numbers:

Def: A number that is divisible only by itself and 1.
Example: 13. 13 is only divisible by 1 and 13. i.e, no other numbers except 1 and 13 divides 13. Hence 13 is a prime number.  

Composite Numbers:

Def: A positive integer that has at least one factor except 1 and the number itself.

Example: 10. 10 is divisible by 1,2,5 and 10. So 10 has two nontrivial factors. Hence 10 is a composite number.

What does divisible by mean?

A numerator or dividend is said to be divisible by a denominator or divisor if and only if the remainder is 0.

Examples: 10 is divisible by 2 because 10/2=(5,0), which implies the remainder is 0.

Divisible

Prime numbers 1 to 100:

2	11	23	31	41	53	61	71	83	97
3	13	29	37	43	59	67	73	89
5	17			47			79
7	19

One thing you must observe that the list starts from 2. No negative numbers are being included in the list. According to the definition of primes, prime numbers can be only positive integers.

What is the fastest way to find a prime number?

There are a few steps in this time-efficient prime number algorithm, which checks whether a number is a prime number or a composite number.

Step1: Compute the square root of the number.

Step2: If the square root is a natural number, then the given number is not a prime. (We are done !)

Else,

It must be a decimal number. Consider it’s next natural number. 

Step3: Then divide the given number with all the primes less than the considered natural number. 

If the given number is divisible by any of the primes then the number is not prime, 

Else, prime!

Example 1:

231 is it a prime?

Step1:

√231 = 15.1..(something no need to calculate the rest decimals)

Step2: 

Square root is not a natural number.

Then, we consider the next natural number of 15.1..  as 16

Step3: Primes below 16 are 2,3,5,7,11,13

Observe 231 is divisible by 3

So, 231 is not a prime.

Example 2:

139 is it a prime?

Step1: 

√139 = 11. 7.. (something no need to calculate the rest decimals)

Step2: 

Square root is not a natural number.

Then, we consider the next natural number of 11.7..  as 12

Step3: 

Primes below 12 are 2,3,5,7,11

Observe that, 139 is not divisible by any one of the above numbers. 

So, 139 is a prime!

Primality test:

This algorithm is one of the most simple and time-efficient algorithm to check prime numbers. The method is called the trial division method. Though this is not a polynomial-time algorithm, one can perform it without using a calculator and other gadgets. There are many sophisticated algorithms are available, viz. Miller–Rabin and Solovay–Strassen primality test [1], Frobenius primality test [2], Agrawal–Kayal–Saxena primality test [3], etc.

Quizzes on prime numbers:

1. Is 0 is a prime number?
Answer: No. (Clear from the above definition )

2.  Is 1 is a prime number and why?
Answer: No. Because 1 is only divisible by 1.

3. What is the only even prime number?
Answer: 2

4. Can prime numbers be negative?
Answer: No. (Clear from the definition of prime numbers)

Check out online prime number checker:
Click here

Check out the following video tutorial:





References:
--------------------------------------------------------------------------------------
[1] Conrad, Keith. "The Miller–Rabin Test." (2016).

[2]  Damgård, Ivan Bjerre, and Gudmund Skovbjerg Frandsen. "An extended quadratic         Frobenius primality test with average and worst case error estimates." International Symposium on Fundamentals of Computation Theory. Springer, Berlin, Heidelberg, 2003.

[3]  Agrawal, Manindra, Neeraj Kayal, and Nitin Saxena. "PRIMES is in P." Annals of mathematics (2004): 781-793.