Return to Answer

I just realized that - well, by definition - you only need to check a number against the primes smaller than the number. In fact only against primes smaller than the numbers square root. So if you are looking for a table of say the first 40000 prime numbers, you could do this:

public int[] nPrimes(int targetNumberOfPrimes) {
    
    int index, candidate;
    
    int[] primes = new int[targetNumberOfPrimes];
    
    while (index < targetNumberOfPrimes) {
        if (candidate < 2) {
            candidate++;
            continue;
        }
        if (isPrime(index, candidate, primes)){
            primes[index] = candidate;
            index++;
        }
        candidate++;
    }
    return primes;
}

private static boolean isPrime(int current, int candidate, int[] primes){
    for (int i = 0; i < current && primes[i] < Math.floor(Math.sqrt(candidate)); i++){
        if (candidate % primes[i] == 0) {
            return false;
        }
    }
    return true;
}

It took my computer about 0.7 seconds for 40000 prime numbers.

I just realized that - well, by definition - you only need to check a number against the primes smaller than the number - not every smaller number. This is the siev of Eratosthenes in the form of an array but not only for 2, 3 and five, but every prime number. In fact you only need to check against primes smaller than the numbers square root. So if you are looking for a table of say the first 40000 prime numbers, you could do this:

public int[] nPrimes(int targetNumberOfPrimes) {
    
    int index, candidate;
    
    int[] primes = new int[targetNumberOfPrimes];
    
    while (index < targetNumberOfPrimes) {
        if (candidate < 2) {
            candidate++;
            continue;
        }
        if (isPrime(index, candidate, primes)){
            primes[index] = candidate;
            index++;
        }
        candidate++;
    }
    return primes;
}

private static boolean isPrime(int current, int candidate, int[] primes){
    for (int i = 0; i < current && primes[i] < Math.floor(Math.sqrt(candidate)); i++){
        if (candidate % primes[i] == 0) {
            return false;
        }
    }
    return true;
}

It took my computer about 0.7 seconds for 40000 prime numbers.

there! Cheers for the square root hint.

I just realized that - well, by definition - you only need to check a number against the primes smaller than the number. In fact only against primes smaller than the numbers square root. So if you are looking for a table of say the first 40000 prime numbers, you could do this:

public int[] nPrimes(int targetNumberOfPrimes) {
    
    int index, candidate;
    
    int[] primes = new int[targetNumberOfPrimes];
    
    while (index < targetNumberOfPrimes) {
        if (candidate < 2) {
            candidate++;
            continue;
        }
        if (isPrime(index, candidate, primes)){
            primes[index] = candidate;
            index++;
        }
        candidate++;
    }
    return primes;
}

private static boolean isPrime(int current, int candidate, int[] primes){
    for (int i = 0; i < current && primes[i] < Math.floor(Math.sqrt(candidate)); i++){
        if (candidate % primes[i] == 0) {
            return false;
        }
    }
    return true;
} 

It took my computer about 0.7 seconds for 40000 prime numbers.

I just realized that - well, by definition - you only need to check a number against the primes smaller than the number. In fact only against primes smaller than the numbers square root. So if you are looking for a table of say the first 40000 prime numbers, you could do this:

public int[] nPrimes(int targetNumberOfPrimes) {
    
    int index, candidate;
    
    int[] primes = new int[targetNumberOfPrimes];
    
    while (index < targetNumberOfPrimes) {
        if (candidate < 2) {
            candidate++;
            continue;
        }
        if (isPrime(index, candidate, primes)){
            primes[index] = candidate;
            index++;
        }
        candidate++;
    }
    return primes;
}

private static boolean isPrime(int current, int candidate, int[] primes){
    for (int i = 0; i < current && primes[i] < Math.floor(Math.sqrt(candidate)); i++){
        if (candidate % primes[i] == 0) {
            return false;
        }
    }
    return true;
}

It took my computer about 0.7 seconds for 40000 prime numbers.

there! Cheers for the square root hint.

I just realized that - well, by definition - you only need to check a number against the primes smaller than the number. In fact only against primes smaller than the numbers square root. So if you are looking for a table of say the first 40000 prime numbers, you could do this:

public int[] nPrimes(int targetNumberOfPrimes) {

int index, candidate;
    
    int[] primes = new int[targetNumberOfPrimes];
    
    while (index < targetNumberOfPrimes) {
        if (candidate < 2) {
            candidate++;
            continue;
        }
        if (isPrime(index, candidate, primes)){
            primes[index] = candidate;
            index++;
        }
        candidate++;
    }
    return primes;
}

private static boolean isPrime(int current, int candidate, int[] primes){
    for (int i = 0; i < current && primes[i] < Math.floor(Math.sqrt(candidate)); i++){
        if (candidate % primes[i] == 0) {
            return false;
        }
    }
    return true;
} 

It took my Computer about 0.7 seconds for 40000 prime numbers.

there! Cheers for the square root hint.

I just realized that - well, by definition - you only need to check a number against the primes smaller than the number. In fact only against primes smaller than the numbers square root. So if you are looking for a table of say the first 40000 prime numbers, you could do this:

public int[] nPrimes(int targetNumberOfPrimes) {
    
    int index, candidate;
    
    int[] primes = new int[targetNumberOfPrimes];
    
    while (index < targetNumberOfPrimes) {
        if (candidate < 2) {
            candidate++;
            continue;
        }
        if (isPrime(index, candidate, primes)){
            primes[index] = candidate;
            index++;
        }
        candidate++;
    }
    return primes;
}

private static boolean isPrime(int current, int candidate, int[] primes){
    for (int i = 0; i < current && primes[i] < Math.floor(Math.sqrt(candidate)); i++){
        if (candidate % primes[i] == 0) {
            return false;
        }
    }
    return true;
} 

It took my computer about 0.7 seconds for 40000 prime numbers.