Find the first N prime numbers. (Method 2)

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 most basic approach to find the first N prime numbers in this post.

• Find the first N prime numbers. (Method 1)

Please go through the post if you are not familiar with the naive methods. They are necessary to learn how the code can be optimized further.

So let us try to further optimize the previously discussed approach.
If you are good at Mathematics, you can easily figure out that for every number all the factors exist in pairs. Now for each pair there is one number that will be smaller than the squareroot of the original number and other one will be greater than the squareroot of the original number. Let us take this by example.
Number = 40
Squareroot = 6.32 ~ 6

FACTORS

You can easily see that there are exactly 4 factors less than 6 and 4 above 6

Number = 36
Squareroot = 6

FACTORS

So, every number if we get its factor upto its square root than that number is not prime or conversely if for any number there in no factor till its squareroot than there is none above that.
Using the above inverse logic we can optimize our logic

private void findPrimes(int limit) {

     // Special handling for 2
     if (limit > 2)
        System.out.print("2,");

     for (int i = 2; i < limit; i++) {

        boolean isPrime = true;

        // Utilizing our previous optimizations
        if (i % 2 == 0) {
            isPrime = false;
        }

        // Get the square root
        int s = (int) Math.sqrt(i);

        // We need to loop only until the square root of that number
        for (int j = 3; j <= s; j += 2) {
            if (i % j == 0) {
                isPrime = false;
            }
        }

        if (isPrime)
            System.out.print(i + ",");
    }

}

The running link for the program can be found here:- http://ideone.com/B2SSJN

Additional methods to find prime numbers:-

• Find the first N prime numbers (Method 3)
• Prime numbers using Sieve of Eratosthenes