Find the first N prime numbers. (Method 3)

By | August 11, 2015

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 thoughts on “Find the first N prime numbers. (Method 3)

  1. persixty
    for (int j = 0; j < primeCount && isPrime; j++) {

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

    Reply
  2. RaHan

    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
  3. Pingback: Find the first N prime numbers. (Method 1) | Study Algorithms

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

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