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

Find the first N prime numbers. (Method 3)

by nikoo28
8 comments 4 minutes read

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 + ",");
}
Code language: Java (java)

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

You might also want to look at an alternate method

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.

nikoo28 July 4, 2017 - 11:41

That is a good thought.

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?

nikoo28 September 15, 2016 - 12:49

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

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.

Prakhar September 16, 2015 - 23:25

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

Harsh Badaya September 18, 2015 - 10:08

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

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

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

Comments are closed.

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