Puedes mejorar el bastante la rapidez de tu programa si aplicas algoritmos para hallar los números primos, en este caso sugiero el algoritmo de Atkin
Matemáticamente deben de cumplirse algunas condiciones matemáticas, las cuales se explican en los métodos applyWheelFactorization y discardSquarePerfects
Con ello generamos un arreglo booleano el cual podemos consultar rápidamente para saber si un número es primo. Sin embargo, este método está limitado al tamaño del arreglo, no a los números primos que realmente quieres. El pro de esto, es que tienes un performance mucho mayor que en otros métodos.
Código propuesto
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class StackOverflow {
public static void main(String[] args) {
SieveOfAtkin sieveOfAtkin = new SieveOfAtkin(600);
int n = 100;
try {
System.out.println(sieveOfAtkin.getNPrimeArray(n));
} catch (IllegalArgumentException e) {
System.out.println("El tamiz de Atkin actual tiene menos de " + n +" números primos");
}
}
private static class SieveOfAtkin {
private final int limit;
private final int sqrt_limit;
private boolean[] sieve;
public SieveOfAtkin(int limit) {
this.limit = limit;
this.sqrt_limit = (int) Math.sqrt(limit);
initSieve();
}
/**
* Devuelve el valor booleano de {@code sieve[number]}
* @param number prime number
* @return {@code sieve[number]}
*/
public boolean isPrime(int number) {
if (number > limit)
throw new IllegalArgumentException("The argument \"number\" must be lesser than \"limit\"");
if (number < 1)
throw new IllegalArgumentException("There are not negative primes");
return sieve[number];
}
/**
* Este método retorna una lista con los primeros {@code n_primes} números primos
* limitado a su existencia dentro de {@code limit}
* @param n_primes indica cuántos números primos deseas obtener
* @return una lista con los primeros {@code n_primes} números primos
* limitado a su existencia dentro de {@code limit}
* @throws IllegalArgumentException si hay menos de n números primos
*/
private List<Integer> getNPrimeArray(int n_primes) throws IllegalArgumentException{
return IntStream.range(2, Integer.MAX_VALUE)
.filter(this::isPrime)
.limit(n_primes)
.boxed()
.collect(Collectors.toList());
}
public void initSieve() {
this.sieve = new boolean[limit];
Arrays.fill(sieve, false);
// SieveOfAtkin funciona únicamente con números mayores a 3
for (int i = 2; i < 4 && i < limit; i++)
sieve[i] = true;
applyWheelFactorization();
discardSquarePerfects();
}
/**
* Cambia sieve[n] a verdadero si alguna de las siguientes
* condiciones se cumple para un par de números enteros
* cualesquiera { (x, y) | x <= sqrt_limit ∩ y <= sqrt_limit }:
* a) Con n = (4 * x * x) + (y * y) tenga un número impar de
* soluciones a la ecuación n % 12 = 1 o n % 12 = 5.
* b) Con n = (3 * x * x) + (y * y) tenga un número impar de
* soluciones a la ecuación n % 12 = 7
* c) Con n = (3 * x * x) - (y * y) | x > y tenga un número impar de
* soluciones a la ecuación and n % 12 = 11
*/
public void applyWheelFactorization() {
for (int x = 1; x <= sqrt_limit; x++) {
for (int y = 1; y <= sqrt_limit; y++) {
// first quadratic using m = 12 and r in R1 = {r : 1, 5}
int n = (4 * x * x) + (y * y);
if (n < limit && (n % 12 == 1 || n % 12 == 5)) {
sieve[n] = !sieve[n];
}
// second quadratic using m = 12 and r in R2 = {r : 7}
n = (3 * x * x) + (y * y);
if (n < limit && (n % 12 == 7)) {
sieve[n] = !sieve[n];
}
// third quadratic using m = 12 and r in R3 = {r : 11}
n = (3 * x * x) - (y * y);
if (x > y && n < limit && (n % 12 == 11)) {
sieve[n] = !sieve[n];
} // end if
}
}
}
/**
* Descarta todos los cuadrados perfectos como números primos, pues
* {@link #applyWheelFactorization() applyWheelFactorization}
* sólo elimina algunos de ellos
*/
public void discardSquarePerfects() {
for (int r = 5; r * r < limit; r++) {
if (sieve[r]) {
for (int i = r * r; i < limit; i += r * r)
sieve[i] = false;
}
}
}
}
}
Comparación de eficiencia
Comparación de performance con el algoritmo propuesto por HowToDoInJava
Resultados de ejecución de los métodos getNPrimeArray en tiempo (nano segundos):
| Intento |
HTDIJ |
Atkins |
Gana |
| 1 |
15738900 |
06870199 |
Atkins |
| 2 |
13388100 |
05334699 |
Atkins |
| 3 |
10170100 |
05314299 |
Atkins |
Como ven la ejecución tarda menos de la mitad en completarse. Los test se corrieron por separado para evitar desventajas de ejecución y para ello se usó el siguiente código de HowToDoInJava:
private static class HowToDoInJavaAlgorithm {
private List<Integer> getNPrimeArray(int n_primes) {
return IntStream.range(2, Integer.MAX_VALUE)
.filter(this::isPrime)
.limit(n_primes)
.boxed()
.collect(Collectors.toList());
}
private boolean isPrime(int number) {
if(number <= 2)
return number == 2;
else
return (number % 2) != 0
&&
IntStream.rangeClosed(3, (int) Math.sqrt(number))
.filter(n -> n % 2 != 0)
.noneMatch(n -> (number % n == 0));
}
}
Lo más importante a ver es que getNPrimeArray es un método bastante tardado, pues genera una Lista, por lo cual no es tan útil para la comparación de eficiencia, por lo tanto, ahora compararemos los métodos isPrime para ver la verdadera diferencia, además de su otra ventaja, pues una vez generado el arreglo o el sieve, se puede usar mucho más rápido para obtener los n números primos.
Si ejecutamos el siguiente código podremos ver la notoria diferencia.
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class StackOverflow{
static final int max = 15_000;
static final int min = 100;
static final int n_test = 100_000;
public static void main (String... args) {
Random random = new Random();
int[] numbers2check = random.ints(n_test, min, max + 1).toArray();
Thread htdij = new Thread(() -> testHtdinjEfficiency(numbers2check));
Thread atkins = new Thread(() -> testAtkinsEfficiency(numbers2check));
htdij.start();
atkins.start();
}
public static void testHtdinjEfficiency(int[] random) {
long[] timing = new long[random.length];
long start = System.nanoTime();
HowToDoInJavaAlgorithm howToDoInJavaAlgorithm = new HowToDoInJavaAlgorithm();
howToDoInJavaAlgorithm.isPrime(random[0]);
timing[0] = System.nanoTime() - start;
for (int i = 1; i < random.length; i++) {
start = System.nanoTime();
howToDoInJavaAlgorithm.isPrime(random[i]);
timing[i] = System.nanoTime() - start;
}
Arrays.sort(timing);
double average = Arrays.stream(timing).average().orElse(Double.NaN);
long frequency_50 = Arrays.stream(timing).filter(e -> e <= 50).count();
System.out.println("htdij\n======\nMin: " + timing[0] + "\tMax: " + timing[random.length -1] +
"\tAverage: " + average + "\nFrequency(n <= 50): " + frequency_50);
}
public static void testAtkinsEfficiency(int[] random) {
long[] timing = new long[random.length];
long start = System.nanoTime();
SieveOfAtkin sieveOfAtkin = new SieveOfAtkin(max + 1);
sieveOfAtkin.isPrime(random[0]);
timing[0] = System.nanoTime() - start;
for (int i = 1; i < random.length; i++) {
start = System.nanoTime();
sieveOfAtkin.isPrime(random[i]);
timing[i] = System.nanoTime() - start;
}
Arrays.sort(timing);
double average = Arrays.stream(timing).average().orElse(Double.NaN);
long frequency_50 = Arrays.stream(timing).filter(e -> e <= 50).count();
System.out.println("Atkins\n======\nMin: " + timing[0] + "\tMax: " + timing[random.length -1] +
"\tAverage: " + average + "\nFrequency(n <= 50): " + frequency_50);
}
}
Mínimo
| Intento |
HTDIJ |
Atkins |
Gana |
| 1 |
0 |
0 |
Empate |
| 2 |
0 |
0 |
Empate |
| 3 |
0 |
0 |
Empate |
Máximo
| Intento |
HTDIJ |
Atkins |
Gana |
| 1 |
6536600 |
3305800 |
Atkins |
| 2 |
18481000 |
3475000 |
Atkins |
| 3 |
25963700 |
4422100 |
Atkins |
Promedio (redondeado)
| Intento |
HTDIJ |
Atkins |
Gana |
| 1 |
776 |
168 |
Atkins |
| 2 |
1399 |
167 |
Atkins |
| 3 |
1236 |
143 |
Atkins |
Frecuencia (timing < 50 ns)
| Intento |
HTDIJ |
Atkins |
Gana |
| 1 |
11110 |
20813 |
Atkins |
| 2 |
15974 |
28628 |
Atkins |
| 3 |
17932 |
30261 |
Atkins |
