loop taking some time and resulting wrong value; first n prime

Question

I'm trying to write a method that gives the collection of first n prime numbers. I googled and many of my code is similar to the ones I found online. but my loop takes long time and print 2, 0 Here's my code

public static boolean isPrime(int numb) {
        if(numb < 0) {
            return false;
        }
        for(int i = 2; i < numb; i++) {
            if((numb % i) != 0) {
                return false;
            }
        }
        return true;

    }

    public static int[] firstPrimeNumbers(int n) {
        int[] pNumbs = new int[n];
        int count = 0;
        int number = 2;
        while(count != n) {
            if(isPrime(number)) {
                pNumbs[count] = number;
                count++;
            }
            number++;
        }
        return pNumbs;
    }




public static void main(String[] args) {

    int[] a = firstPrimeNumbers(2);
    for(int x: a) {
        System.out.println(x);
    }
}

Just a little micro-opt: the only even prime is 2. After that you can skip the even numbers (`i += 2`) — Rogue, Aug 14 '19 at 18:37
`if((numb % i) != 0) { return false;}` that means that if is is **not** divisible by `i` (has some rest) it is not a prime? shouldn't it be `== 0`, that is, if divisible by `i` then it is not a prime — user85421, Aug 14 '19 at 18:37
second optimization: you only need to test divisors up to the square root of the number... — user85421, Aug 14 '19 at 18:51
@CarlosHeuberger not sure what you mean, does that make any difference? — rosababy, Aug 14 '19 at 19:08
to test if `n` is prime, you need only to check divisors up to `sqrt(n)` instead of `n` - makes some difference in time needed because less then half have to be tested. e.g. to test if `11` is prime, only division by `2` and `3` need to be tested; same for `21`; for `27` you must test `2`, `3`, `5` — user85421, Aug 14 '19 at 22:25
see link in William's answer: [Why do we check up to the square root of a prime number to determine if it is prime?](https://stackoverflow.com/q/5811151/85421) (or on right side under Linked), also do not forget Rogue's [optimization](https://stackoverflow.com/questions/57500245/loop-taking-some-time-and-resulting-wrong-value-first-n-prime?noredirect=1#comment101470030_57500245) (no need to test `4`, `6`, `8`, ... since already testing `2`) — user85421, Aug 14 '19 at 22:44

geco17 · Accepted Answer · 2019-08-14T19:40:39.820

One of the most common algorithms is the Sieve of Eratosthenes. There are several optimizations that can be done but this is a java implementation of the algorithm. You only need to go up to the square root of the number because if the number is not prime, at least one of its factors will be the square root of the number in question. See here as well.

int[] primes(int num) {
    boolean[] bool = new boolean[num];
    Arrays.fill(bool, true);
    int count = num;
    for (int i = 2; i < Math.sqrt(num); i++) {
        if(bool[i]) {
            for(int j = (i * i); j < num; j = j + i) {
                bool[j] = false;
                count--;
            }
        }
    }
    int[] primes = new int[count];
    for (int i = 2; i< bool.length; i++) {
        if(bool[i]) {
            primes[count - 1] = i;
        }
    }
    return primes;
}

EDIT

As some users have mentioned in the comments:

I made a mistake, creating an array of the primes up to the number num (input value) but instead the question asks for the first num primes.
The OP's code has a typo on the numb % i check.

As such I've modified the code as follows:

int[] primes(int num) {
    if (num < 1) {
        return new int[0];
    }
    int[] primes = new int[num];
    int curTest = 2;
    int count = 0;
    while (count < num) {
        if (isPrime(curTest)) {
            primes[count] = curTest;
            count++;
        }
        curTest++;
    }
    return primes;
}

boolean isPrime(int test) {
    for (int i = 2; i <= Math.sqrt(test); i++) {
        if (test % i == 0) {
            return false;
        }
    }
    return true;
}

The input `num` is the number (*count*) of primes to find, not the max. prime to find. E.g. result of `firstPrimeNumbers(10)` should be `[2,3,5,7,11,13,17,19,23,29]`, not `[2,3,5,7]`. --- The problem with the question code is a simple typo(?), as [identified by Carlos Heuberger](https://stackoverflow.com/questions/57500245/loop-taking-some-time-and-resulting-wrong-value-first-n-prime#comment101470040_57500245). — Andreas, Aug 14 '19 at 19:04

loop taking some time and resulting wrong value; first n prime

1 Answers1