Efficient Algorithms to Generate Prime Numbers

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approaches to find out if a number is prime. Let's find out if P is a prime number.

Approach 1: Divide P by all the numbers from 2 to P - 1. If any of these numbers is divided by P then P is not a prime number. The algorithm below returns false if P is divisible by any number between 2 and P - 1. Otherwise, P is a prime number and returns true. 

// This method takes one parameter P
                      // to check if P is prime
                      public boolean isPrime(int P) {
                      	for(int i = 2; i < P; ++i) {
                      		if(P % i == 0) return false;
                      	}
                      	return true;	
                      }

Select all Open in new window

Approach 2: Whenever there is a divisor greater than square-root(P), there must be another divisor less than or equal to square-root(P) but NOT greater than square-root(P). For example: Divisors of 20 are: 20 = 1, 2, 4, 5, 10 and 20. For each of these pairs there MUST be least one divisor that is less than or equal to square-root(P).
20 = 1 X 20
20 = 2 X 10
20 = 4 X 5

If we stopped finding divisors when current divisor i is 4, we could still get all the divisors. So, instead of looking for all numbers between 2 and (P - 1) we can do 2 to sqrt(P) which gives a faster solution.

public boolean isPrime(int P) {
                          // i * i <= P is similar to i <= sqrt(p)    
                      	for(int i = 2; i * i <= P; ++i) {
                      		if(P % i == 0) return false;
                      	}
                      	return true;
                      }

Select all Open in new window

Approach 3: The only prime number that is even is 2. Any other even number cannot be prime because all even numbers are divisible by 2. So, instead of dividing by all the numbers in range 0 to (P - 1) we’ll divide only by odd numbers up to sqrt(P).

public boolean isPrime(int P) {
                      	if(P == 2) return true;
                      	else {
                      		for(int i = 3; i * i <= P; i = i + 2) {
                      			if(P % i == 0) return false;
                      		}
                      	}
                      	return true;	
                      }

Select all Open in new window

Approach 4: Suppose we need to find prime numbers between 1 and 25. The algorithms described above are capable of providing a result but are not optimal. We might have to divide by the same divisor over and over again. For example, we are checking if each of the dividends below are being divided by 2 and 3.

1. Is 15 Prime? Divide 15 by 2 and 3 (2 to sqrt(15))
2. Is 20 Prime? Divide 20 by 2, 3 and 4 (2 to sqrt(20))
3. Is 25 Prime? Divide 20 by 2, 3, 4 and 5 (2 to sqrt(20))

There is another approach that finds prime numbers in a range optimally. Let's check steps for that algorithm while finding all prime numbers between 1 and 25. The first prime number is 2. Discard all multiples of 2 (except 2 itself) as they must not be prime numbers. Multiples of a prime number P or any natural number CANNOT be prime, ignoring multiplcation by 1.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Now discard multiples of 3
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

As we know that there will be not be a new prime number once we reach sqrt(n) we will continue this process until we reach sqrt(25) or 5. That is, discard all multiples of 2, 3, 4 and 5. This ancient algorithm is known as Sieve of Eratosthenes.

Discard multiples of 4
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Discard multiples of 5
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

The remaining numbers are 2, 3, 7, 11, 13, 17, 19 and 23. Each of these numbers is prime. This method is very fast in cases where we need to search for prime numbers in a gigantic range.

In this algorithm below, there is a boolean array that stores prime values of numbers 0 - 50000. Initially, all of them are false. Take each of the numbers less than sqrt(50000) and mark all of their multiples as false. Then store the values of p[] that are marked as true into prime[] which is the array of all prime numbers in a range. To be clear,

p[] = array that contains boolean values for all the numbers in a range
prime[] = array that contains prime numbers in a range

In the above example, we have 2, 3, 7, 11, 13, 17, 19 and 23 that are marked as true after exclusion. So, simply copy these values to prime[] array. prime[] = {2, 3, 7, 11, 13, 17, 19, 23}

In this way, we have an array that contains ONLY prime numbers (remember, p[] had boolean values for numbers 0 - 25 but we are only interested in prime numbers. So, we copied prime numbers into another array.) Suppose if we are asked to find first eight prime numbers we could easily print the numbers in index 0 to 7 of prime[] array.

boolean[] p = new boolean[50000];
                      
                      public int[] prime(int n) {
                          // Initially, mark all numbers as prime
                          for(int i = 0; i <= n; ++i) 
                              p[i] = true;
                          // 0 and 1 are not prime numbers
                      	p[0] = p[1] = false;
                      	for(int i = 2; i * i <= n; ++i) {
                      		if(p[i] == true) {
                      			for(int j = i + i; j <= n; j = j + i) {
                      				// mark multiples of i as non-prime    
                      				p[j] = false;
                      			}
                      		}
                      	}
                      	int k = 0;
                          // prime[] harvests prime numbers
                          int[] prime = new int[n/4]; 
                      	for(int i = 0; i <= n; ++i) {
                      		if(p[i] == true) {
                      			prime[k++] = i;
                      		}
                      	}
                          return prime;
                      }

Select all Open in new window