Home Misc Find the first N prime numbers. (Method 3)

Find the first N prime numbers. (Method 3)

by Harsh Badaya
8 comments

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

8 comments

You may also like

8 comments

persixty July 3, 2017 - 20:55
for (int j = 0; j < primeCount && isPrime; j++) {

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

Reply
nikoo28 July 4, 2017 - 11:41

That is a good thought.

Reply
onefooted September 9, 2016 - 04:39

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

Reply
nikoo28 September 15, 2016 - 12:49

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

Reply
RaHan May 24, 2016 - 20:16

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.

Reply
Prakhar September 16, 2015 - 23:25

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

Reply
Harsh Badaya September 18, 2015 - 10:08

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

Reply
Find the first N prime numbers. (Method 1) | Study Algorithms August 11, 2015 - 14:18

[…] Find the first N prime numbers. (Method 3) […]

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More