Mathematical Algorithms – Prime numbers and Primality Tests

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

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

• Prime Numbers
• Left-Truncatable Prime
• Mersenne Prime
• Super Prime
• Palindromic Primes
• Almost Prime Numbers
• Pernicious number
• Twisted Prime Number
• Newman–Shanks–Williams prime
• Recursive program for prime number
• Co-prime pair with given sum minimum difference
• Check whether a number is Emirpimes or not
• Check if a number is sandwiched between primes
• Check whether a number is semiprime or not
• Check if two numbers are co-prime or not

• Special prime numbers
• Sophie Germain Prime
• Balanced Prime
• Prime Triplet
• 2^x + 1 and Prime
• Check if a number is Full Prime
• Check whether a number is circular prime or not
• Check whether given three numbers are adjacent primes
• Print prime numbers from 1 to N in reverse order
• Program to find sum of prime numbers between 1 to n
• Find two prime numbers with given sum
• Count Primes in Ranges
• Queries for maximum difference between prime numbers in given ranges

• Twin Prime Numbers
• Pierpont Prime
• Prime numbers and Fibonacci
• The Ulam Spiral
• Find coordinates of a prime number in a Prime Spiral
• Program for Goldbach’s Conjecture (Two Primes with given Sum)
• Circular primes less than n
• Check a number for Permutable Prime
• N expressed as sum of 4 prime numbers
• Check if a number can be written as a sum of ‘k’ prime numbers
• Express an odd number as sum of prime numbers
• Find the prime numbers which can written as sum of most consecutive primes
• Finding a Non Transitive Coprime Triplet in a Range

Quick Links:

• Recent Articles on Prime Number
• Practice problems on Mathematical algorithms