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

We discussed the basic approaches to find the first N prime numbers in these posts

It is advised that you go through the above posts to get a basic understanding of the approach that we have used to determine the prime numbers.

Now lets analyze our problem once again for last time. In all the above approaches we are matching our number with all the numbers before it to determine if it’s a prime or not. The logic we are using is that if there isn’t any number other than 1 and itself with which its modulo is zero then that number is prime. So why not use this result further to find the next prime numbers and develop an intelligent algorithm that knows what it has done before and use those results further to optimize itself.

Any number that is not prime is always divisible by at least one prime that comes before it in the number series.

Example:-

2 is prime factor of 40.

2, 3 are prime factors of 36.

So conversely we can say that if any number doesn’t divide itself with all the prime numbers before it then that number is also prime OR modulo of that no. with all the prime numbers before that is non-zero then that number is also prime.

So lets use this logic and develop our final algorithm.

private void findPrimes(int limit) { int[] primes = new int[100]; // Special handling for the integer '2' primes[0] = 2; // Number of primes encountered int primeCount = 1; // Looping from 3, to the limit for (int i = 3; i < limit; i++) { boolean isPrime = true; if (i % 2 == 0) { continue; } for (int j = 0; j < primeCount; j++) { if (i % primes[j] == 0) { isPrime = false; } } // Store the prime number and increment the count if (isPrime) { primes[primeCount++] = i; } } // Print the primes for (int x : primes) if (x != 0) System.out.print(x + ","); }

Here is the ideone link of the running code:- http://ideone.com/1GWu49

You might also want to look at an alternate method

to avoid continuing to check when a candidate is already identified as composite.

That is a good thought.

Why not increment the loop in two’s (i=i+2) and avoid the check of %2 each iteration?

Yes, that can be done. Thanks for pointing it out. I will correct it.

Again, apparently minor language issues throw off the logic. It is not ALL prime numbers before it but ANY prime before it. Take 9 for example. It is not divisible by 7 which is a prime before 9 and yet 9 și not prime. Also see my comment under method 1. Precision and and accuracy are paramount in these problems. Incorrect problem specifications and definitions throw the logic completely off.

Complexity will be less than O(N^1.5)..?

yes, it should be less than N^3/2.

Pingback: Find the first N prime numbers. (Method 1) | Study Algorithms