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.

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

1 | 40 |

2 | 20 |

4 | 10 |

5 | 8 |

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

**Number = 36**

** Squareroot = 6**

FACTORS

1 | 36 |

2 | 18 |

3 | 12 |

4 | 9 |

6 | 6 |

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:-

Pingback: Find the first N prime numbers. (Method 3) | Study Algorithms

Pingback: Find the first N prime numbers. (Method 1) | Study Algorithms