What is Prime Number?

A prime number is a natural number greater than 1 that is divisible by only 1 and the number itself.

In other words, the prime number can be defined as a positive integer greater than that has exactly two factors, 1 and the number itself. First 10 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Note: 1 is neither a prime number nor a composite number. All other numbers can be classified as prime or composite.

Some important theorems related to prime numbers are mentioned here:

• Hardy-Ramanujan Theorem
• Rosser’s Theorem
• Fermat’s little theorem
• Euclid Euler Theorem
• Euclid’s Lemma
• Bertrand’s Postulate
• Legendre’s Conjecture

What is Primality Test?

Primality Test is an algorithm to determine whether a number is prime or not.

Unlike integer factorization, primality test only states if the input is prime or not and does not generally provide prime factors. Some of the frequently used primality test algorithms are stated below