Algorithms
Prime numbers less than equal to N in O(n) time
Given an integer N, find all the prime numbers less than in sorted order.
A trivial solution would be to loop through all numbers from 2 to N and check if a number is prime or not. How can we check if a number is prime ? Note that a number is a prime if it has no factor other than 1 and the number itself. So, if we want to check if a number k is prime we need to check that there is no number by which k is divisible. But we don’t actually need to check all numbers because maximum number that can divide the number k without any remainder is √k. So, we can check is a number is prime by checking than k is not divisible by all number from 2 to √k. So, to find all primes less than n will take O(n√n) time.
public boolean isPrime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if ((n & 1) == 0) return false;
int rootN = (int)Math.sqrt(n);
for (int i=2; i<=rootN; ++i) {
if (n % i == 0) return false;
}
return true;
}
Faster Solution – Sieve_of_Eratosthenes
This problem can be solved by a famous problem widely known as Sieve of Eratosthenes. Read this article for a better understanding. However, I am taking their example in my post to explain the solution.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:
- Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
- Initially, let p equal 2, the first prime number.
- Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).
- Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
Example (from wiki)
To find all the prime numbers less than or equal to 30, proceed as follows.
First generate a list of integers from 2 to 30:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
First number in the list is 2; cross out every 2nd number in the list after it by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):
2 3456789101112131415161718192021222324252627282930
Next number in the list after 2 is 3; cross out every 3rd number in the list after it by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):
2 3456789101112131415161718192021222324252627282930
Next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after it by counting up from 5 in increments of 5 (i.e. all the multiples of 5):
2 3456789101112131415161718192021222324252627282930
Next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number in the list after 7, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7*7 is greater than 30. The numbers left not crossed out in the list at this point are all the prime numbers below 30:
2 3 5 7 11 13 17 19 23 29
The main idea here is that every value for p is prime, because we have already marked all the multiples of the numbers less than p. Note that some of the numbers being marked may have already been marked earlier (e.g., 15 will be marked both for 3 and 5).
As a refinement, it is sufficient to mark the numbers in step 3 starting from p^2, as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p2 is greater than n.[1]
Below is a O(n) time code for the above algorithm:
// all primes between 1 to N: Use Sieve of Eratosthenses
public static Set<Integer> allPrimes(final int N) {
final boolean[] flag = new boolean[N];
final Set<Integer> primes = new TreeSet<Integer>();
for (int i = 0; i < N; i++) {
flag[i] = true;
}
for (int i = 0; i < Math.sqrt(N); i++) {
if (flag[i] == true) {
primes.add(i);
for (int j = i * i; j < N; j += i) {
flag[j] = false;
}
}
}
return primes;
}