Question: Given an integer N, find the prime numbers in that range from 1 to N.
Input: N = 25
Output: 2, 3, 5, 7, 11, 13, 17, 19, 23
Today let us discuss about a very common but very interesting problem “To find prime numbers in first N Natural numbers “. I will be taking here a very specific approach of first giving definition of prime numbers , using that definition to derive the algorithm, and then using different properties or results that can be further applied to our algorithm to optimize it.
So let us start with the definition of prime numbers.
“Prime numbers are the natural numbers whose factors are 1 and themselves “. So if any number X is prime number then it should have exactly two factors 1 and X. This implies that all the number greater than 1 and less than X shouldn’t divide X to remainder 0. (X % num != 0)
So let us use this statement of ours to derive our very first algorithm to solve the problem.
This will be a naive approach, using 2 loops one outer loop for every number and inner loop that for every number will go upto (j=number-1) and check if anytime modulo of i with j comes 0 then this number is not prime.
void findPrimes(int limit) {
// Loop from the first Prime till limit
for (int i = 2; i < limit; i++) {
// Assume number to be prime
boolean isPrime = true;
// Loop from 2 to the number to checked
for (int j = 2; j < i; j++) {
// If the number divides, it means the number is not prime
if (i % j == 0) {
isPrime = false;
break;
}
}
// Print the number if it is prime
if (isPrime)
System.out.print(i + ",");
}
}
Above is a very naïve approach. If you know little maths you will know that this can be optimized by checking it till i/2 I.e. making inner loop to go to half of values. Furthur you can optimize by checking only for 2 and then all the odd numbers that is incrementing the inner loop by 2. So now let us use this result and refine our algorithm.
void findPrimes(int limit) {
// Special handling for 2
if (limit > 2)
System.out.println("2,");
// Loop from the first Prime till limit
for (int i = 2; i < limit; i++) {
// Assume number to be prime
boolean isPrime = true;
if (i % 2 == 0)
isPrime = false;
else {
// Loop from 3 to number/2
for (int j = 3; j < i / 2; j += 2) {
// If the number divides, it means the number is not prime
if (i % j == 0) {
isPrime = false;
break;
}
}
}
// Print the number if it is prime
if (isPrime)
System.out.print(i + ",");
}
}
Here is a link of the running code:- http://ideone.com/BGr3b0
Time Complexity:- O(n2)
Space Complexity:- O(1)
To further optimize this approach visit these links:-