Site icon Study Algorithms

Find the first N prime numbers. (Method 3)

nikoo28

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

Exit mobile version