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

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

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

Today let us discuss about a very common but very interesting problem “To find prime numbers in first N Natural numbers “. I will be taking here a very specific approach of first giving definition of prime numbers , using that definition to derive the algorithm, and then using different properties or results that can be further applied to our algorithm to optimize it.

“Prime numbers are the natural numbers whose factors are 1 and themselves “. So if any number X is prime number then it should have exactly two factors 1 and X. This implies that all the number greater than 1 and less than X shouldn’t divide X to remainder 0. (X % num != 0)

So let us use this statement of ours to derive our very first algorithm to solve the problem.

This will be a naive approach, using 2 loops one outer loop for every number and inner loop that for every number will go upto (j=number-1) and check if anytime modulo of i with j comes 0 then this number is not prime.

void findPrimes(int limit) {

// Loop from the first Prime till limit
for (int i = 2; i < limit; i++) {
// Assume number to be prime
boolean isPrime = true;

// Loop from 2 to the number to checked
for (int j = 2; j < i; j++) {

// If the number divides, it means the number is not prime
if (i % j == 0) {
isPrime = false;
break;
}
}

// Print the number if it is prime
if (isPrime)
System.out.print(i + ",");
}
}


Above is a very naïve approach. If you know little maths you will know that this can be optimized by checking it till i/2 I.e. making inner loop to go to half of values. Furthur you can optimize by checking only for 2 and then all the odd numbers that is incrementing the inner loop by 2. So now let us use this result and refine our algorithm.

void findPrimes(int limit) {

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

// Loop from the first Prime till limit
for (int i = 2; i < limit; i++) {
// Assume number to be prime
boolean isPrime = true;

if (i % 2 == 0)
isPrime = false;
else {

// Loop from 3 to number/2
for (int j = 3; j < i / 2; j += 2) {

// If the number divides, it means the number is not prime
if (i % j == 0) {
isPrime = false;
break;
}
}
}

// Print the number if it is prime
if (isPrime)
System.out.print(i + ",");
}
}


Here is a link of the running code:- http://ideone.com/BGr3b0

Time Complexity:- O(n2)
Space Complexity:- O(1)

To further optimize this approach visit these links:-

#### You may also like

October 21, 2017 - 02:24

Plz send me algorithm of prime number not code

December 25, 2017 - 16:39

The algorithm has been discussed in the post. Please let me know where are you facing a problem?

May 27, 2016 - 19:02

Hi nikoo,

The body of the problem says as you say, the title says it like I say, “the first N”.

May 24, 2016 - 20:07

2 problems with the article. 1. N=25 means I expect 25 prime numbers as the answer. 2. The definition of a prime number is incorrect. ANY number is divisible by either 1 or itself. It should be “ONLY 1 and itself”.

May 27, 2016 - 10:44

Hi Rahan,

If you read the question properly, it says to print prime numbers in the range of 1-N. It never says to print N prime numbers.

August 11, 2015 - 14:17

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

August 11, 2015 - 14:16

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