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

Find the first N prime numbers. (Method 1)

by nikoo28
7 comments 5 minutes read

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.

So let us start with the definition of prime numbers.

“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

7 comments

Nimra October 21, 2017 - 02:24

Plz send me algorithm of prime number not code

nikoo28 December 25, 2017 - 16:39

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

RaHan 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”.

RaHan 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”.

nikoo28 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.

Find the first N prime numbers. (Method 2) | Study Algorithms August 11, 2015 - 14:17

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

Find the first N prime numbers. (Method 3) | Study Algorithms August 11, 2015 - 14:16

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

Comments are closed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More