Prime Numbers

Properties, Conjectures and Theorems

Definition: A prime number is a number greater than 1 that has exactly two positive integer divisors, 1 and itself.

  1. 1 is neither a prime, nor a composite.
  2. 2 is the only even prime.
  3. Only consecutive primes are 2 and 3.
  4. Every prime number can represented in form of 6n±1 except 2 and 3, where n is natural number.
  5. There are infinitely many primes. (Euclid’s Theorem)
  6. Prime Number Theorem - The number of primes till n are approximately equal to n /ln (n) when n is large. Alternatively, the probability that a given, randomly chosen number n is prime is inversely proportional to its number of digits, or to the logarithm of n.
  7. Goldbach’s conjecture - Every even integer greater than 2 can be expressed as the sum of two primes.
  8. Lemoine’s conjecture - Any odd integer greater than 5 can be expressed as a sum of an odd prime and an even semiprime.
  9. Legendre’s Conjecture - It says that there is always one prime number between any two consecutive natural number’s (n = 1, 2, 3, 4, 5, …) square.
  10. Bertrand’s postulate - Bertrand’s postulate is a theorem stating that for any integer n > 3, there always exists at least one prime number p with n < p < 2n-2.
  11. GCD of 2 primes is always 1.
  12. Euclid’s lemma - If a prime p divides a * b, then, p divides at least one of a and b. For example, 2|(6*9) => 2|6. This may or may not be true for any non-prime instead of p.
  13. Hardy-Ramanujan Theorem - The number of prime factors of n will approximately be log(log(n)) for most natural numbers n.
  14. Rosser’s Theorem - The nth prime number is greater than the product of n and natural logarithm of n for all n greater than 1. Mathematically, For n >= 1, if p is the nth prime number, then p > n * (ln n).
  15. Fermat’s Little Theorem
  16. Euclid Euler Theorem
  17. Ulam Spiral or Prime Spiral

Other interesting Numbers

  1. Co-Primes - Two numbers, a and b are said to be co-prime iff gcd(a,b) = 1. Two conecutive numbers are always co-prime. Any prime number is co-prime with every other number.

  2. Twin Prime - A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair (11, 13). In other words, a twin prime is a prime that has a prime gap of two.

  3. Prime Triplet - Prime Triplet is a set of three prime numbers of the form (p, p+2, p+6) or (p, p+4, p+6).

  4. Semiprime - A semiprime number is a natural number that is a product of two prime numbers. Semiprimes include the squares of prime numbers. Because there are infinitely many prime numbers, there are also infinitely many semiprimes. Ex - 4, 6, 9, 10, 14, 15…

  5. Mersenne Primes - A Mersenne prime is a prime that can be expressed as 2p-1, where p is a prime number. They are extremely rare. Note that having the form of 2p-1 does not guarantee that the number is prime. Ex - 211-1 is not a prime. The largest known prime is a Mersenne Prime discovered using Lucas-Lehmer Series.

  6. Emirps - An emirp (prime spelled backwards) is a prime number that results in a different prime when its decimal digits are reversed. This definition excludes the related palindromic primes. The term reversible prime may be used to mean the same as emirp, but may also, ambiguously, include the palindromic primes. Ex - 13, 17, 31, 37, 71, 73, 79, 97, 107, 113, …

  7. Special Primes - A prime number is said to be Special prime number if it can be expressed as the sum of three integer numbers: two neighboring prime numbers and 1. For example, 19 = 7 + 11 + 1, or 13 = 5 + 7 + 1.

  8. Left and Right Truncatable Prime - If we keep on removing a digit from left or right, the number still remains a prime. Ex - 317.

  9. Super Primes - also known as higher order primes are the subsequence of prime numbers that occupy prime-numbered positions within the sequence of all prime numbers. First few Super-Primes are 3, 5, 11 and 17. Since, 3 occupies the 2nd position and so on…

  10. Palindromic Primes - sometimes called a palprime is a prime number that is also a palindromic number. Ex - 2, 3, 5, 7, 11…

  11. Sophie Germain Prime - A prime number p is called a sophie prime number if 2p+1 is also a prime number. The number 2p+1 is called a safe prime. For example 11 is a prime number and 11*2 + 1 = 23 is also a prime number so, 11 is sophie germain prime number.

  12. Almost Prime - A k-Almost Prime Number is a number having exactly k prime factors (not necessary distinct) For example, 2, 3, 5, 7, 11 ….(in fact all prime numbers) are 1-Almost Prime Numbers as they have only 1 prime factors (which is themselves). 4, 6, 9…. are 2-Almost Prime Numbers as they have exactly 2 prime factors (4 = 2*2, 6 = 2*3, 9 = 3*3) Similarly 32 is a 5-Almost Prime Number (32 = 2*2*2*2*2) and so is 72 (2*2*2*3*3).

  13. Pernicious Number - A pernicious number is a positive integer which has prime number of ones in its binary representation. The first pernicious number is 3 since 3 = (0011)(in binary representation) and 1 + 1 = 2, which is a prime.

  14. Twisted Prime - If a prime’s reverse is also a prime number. Ex - 31 and 13.

  15. Balanced Prime - If a prime is equal to the (sum of its neighbours) / 2. Ex - 5, 53, 157, 173, …

  16. Sexy Prime - In mathematics, Sexy Primes are prime numbers that differ from each other by six. For example, the numbers 5 and 11 are both sexy primes, because they differ by 6. For a prime p, if p + 2 or p + 4 (where p is the lower prime) is also prime.

  17. Pierpont Prime - A Pierpont Prime is a prime number of the form p = 2l.3k + 1 (having factors 2 and 3 only + 1). First few Pierpont prime numbers are 2, 3, 5, 7, 13, 17, 19, 37, 73, 97, 109, …

  18. Newman–Shanks–Williams Prime

  19. Fermat Numbers - A number of the form 2x + 1 (where x > 0) is prime if and only if x is a power of 2, i.e., x = 2n. So overall number becomes 22n + 1. The first few Fermat numbers are 3, 5, 17, 257, 65537, 4294967297, … An important thing to note is a number of this is not always prime.

  20. Circular Prime - A prime number is a Circular Prime Number if all of its possible rotations are itself prime numbers.

  21. Permutable Prime - A Permutable prime number is that number which after switching the position of digits through any permutation is also prime. Some of the permutable prime numbers are 2, 3, 5, 7, 11, etc.

Primality Tests

1. School Method

Uses the fact that a composite number must have atleast one prime factor till sqrt(n) (obviously).

Link: https://www.geeksforgeeks.org/primality-test-set-1-introduction-and-school-method/

Time = O(√n)

//School Method. Time = O(sqrt(n))
bool isPrime(int n)
{
	if(n <= 1) return false;

	for(int i = 2; i*i <= n; i++)		//better than using sqrt()
	{
		if(n % i == 0) return false;
	}

	return true;
}

1.1 Optimized School Method

Time = O(√n)

Optimization: We can check only odd numbers after 2 in the range 3 to sqrt(n).

bool isPrime(int n) 
{ 
    // check if n is a multiple of 2 
    if (n % 2 == 0) 
        return false; 
  
    // if not, then just check the odds 
    for (int i = 3; i * i <= n; i += 2)  
        if (n % i == 0) 
            return false;     
    return true; 
}

Optimization: We can check only numbers of the form 6k±1 in the range 2 to sqrt(n).

bool isPrimeOptimized(int n)
{
	if(n <= 1) return false;
	if(n <= 3) return true;

	//remove multiples of 2 and 3
	if(n % 2 == 0 || n % 3 == 0)
		return false;

	//from 5 check all multiples of the form 6k±1 (prime factors only)
	for (int i = 5; i*i <= n; i += 6)
	{
		if(n % i == 0 && n % (i+2) == 0)
			return false;
	}

	return true;
}

2. Fermat’s Method

Probabilistic test based on Fermat’s Little Theorem. Carmichael numbers are composite numbers which fail this test. Carmichael numbers are also called Fermat pseudoprimes.

Link: https://www.geeksforgeeks.org/primality-test-set-2-fermet-method/

If p is a prime number, then for every a, 1 < a < p-1,
ap-1 ≡ 1 (mod p) OR ap-1 % p = 1

3. Miller-Rabin Test

This method is a probabilistic method (Like Fermat), but it generally preferred over Fermat’s method.

Link: https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/

4. Solovay-Strassen Test

Link: https://www.geeksforgeeks.org/primality-test-set-4-solovay-strassen/

5. Lucas Primality Test

Link: https://www.geeksforgeeks.org/lucas-primality-test/

6. Lucas-Lehmer Series

Link: https://www.geeksforgeeks.org/primality-test-set-5using-lucas-lehmer-series/

7. AKS Primality Test

Galactic Algorithm

Link: https://www.geeksforgeeks.org/aks-primality-test/

8. Wilson’s Theorem

Link: https://www.geeksforgeeks.org/wilsons-theorem/ Link: https://www.geeksforgeeks.org/implementation-of-wilson-primality-test/

9. Vantieghems Theorem for Primality Test

Checks primes only till 11.

Link: https://www.geeksforgeeks.org/vantieghems-theorem-primality-test/

10. Lehmann’s Primality Test

Link: https://www.geeksforgeeks.org/lehmanns-primality-test/

Find all primes upto N (Sieves)

Sieve of Eratosthenes

Time = O(n * log(log(n)))

Complexity Analysis: https://www.geeksforgeeks.org/how-is-the-time-complexity-of-sieve-of-eratosthenes-is-nloglogn/

Algorithm:

  1. Create a list of numbers from 0 to n (size = n+1), and mark all as 1/true, mark 0 and 1 as 0 (they aren’t prime)
  2. Start from 2 and,
  3. Check if 1, if it is then mark all its multiples from i*i till n as 0 (because if we’re at i, then every number till i*i is already marked)
  4. Repeat this while i <= sqrt(n) (all numbers till sqrt(n)*sqrt(n) (n) will get marked)
void primeSieve(int n)
{
	vector<int> s(n + 1, 1);		//seive size = n+1, default all to 1
	s[0] = s[1] = 0;

	for (int i = 2; i * i <= n; i++)
	{
		if (s[i] == 1)
			for (int j = i * i; j <= n; j += i)
				s[j] = 0;
	}

	for (int i = 0; i < s.size(); i++)		//display
		if (s[i] == 1)
			cout << i << " ";
}

Time Complexity:

n * (1/2 + 1/3 + 1/5 + ... + 1/n)

=> n * (this is a Harmonic Progression) 

=> n * (log log n)

Sieve of Eratosthenes in 0(n) time complexity

Link: https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/

Sieve Of Sundaram

Time = O(n log n) (Slower than linear Eratosthenes)

Algorithm:
SOS can find all primes upto 2*n+2 for a given n.

  1. Calculate newN = (n-1)/2, Make a sieve of size nNew+1 and mark all in sieve as false,
  2. Mark all numbers of the form i + j + 2ij as true where 1 <= i <= j,
  3. Print 2,
  4. Remaining primes are of the form 2i + 1 where i is index of NOT (false) marked numbers. So print 2*i + 1 for all i such that sieve[i] is false.
bool sieveSundaram(int n)
{
	int nNew = (n - 1) / 2;

	bool s[nNew + 1];
	memset(s, false, sizeof(s));

	// Main logic of Sundaram.  Mark all numbers of the
	// form i + j + 2*i*j as true where 1 <= i <= j
	for (int i = 1; i <= nNew; i++)
		for (int j = i; (i + j + 2 * i * j) <= nNew; j++)
			s[i + j + 2 * i * j] = true;

	// Print 2
	if (n > 2)
		cout << 2 << " ";

	// Print other primes. Remaining primes are of the form
	// 2*i + 1 such that marked[i] is false.
	for (int i = 1; i <= nNew; i++)
		if (s[i] == false)
			cout << 2 * i + 1 << " ";

  return 0;
}

Goldbach’s Conjecture and Applications

//Loop for checking and printing all prime sum pairs
for (int i = 2; i <= n/2; ++i)
	{
		if(isPrime(i) && isPrime(n - i))		// if(s[i] && s[n-i])
			{
				cout << i << ", " << (n - i);
			}
	}

Application

  1. Express even number as sum of two primes (Direct application)
  2. Express odd number as sum of atmost three primes
  3. If N can be expressed as sum of four primes
  4. If N can be written as sum of K prime numbers

References

  1. https://www.geeksforgeeks.org/mathematical-algorithms/mathematical-algorithms-prime-numbers-primality-tests/
  2. https://procoderforu.com/prime-numbers
  3. Brilliant Wiki
    i. Prime Numbers
    ii. Infinitely Many Primes
    iii. Distribution of Primes
    iv. Mersenne Prime
  4. Theorems and Conjectures involving prime numbers