java - reglas - ¿Cómo genero Primes usando la regla 6*k+- 1?

regla de 6x6 en power point

Question

Sabemos que todos los números primos superiores a 3 pueden generarse usando:

6 * k + 1
6 * k - 1

Sin embargo, todos los números generados a partir de las fórmulas anteriores no son primos.

For Example:
6 * 6 - 1 = 35 which is clearly divisible by 5.

Para eliminar tales condiciones, usé un método de tamiz y eliminando los números que son factores de los números generados a partir de la fórmula anterior.

Usando los hechos:

Se dice que un número es primo si no tiene factores primos.

1. Como podemos generar todos los números primos usando las fórmulas anteriores.
2. Si podemos eliminar todos los múltiplos de los números anteriores, solo nos quedan números primos.

Para generar primos por debajo de 1000.

ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
int n = 1000;
for (int i = 1; i <= (n / 6) ; i++) {
//get all the numbers which can be generated by the formula
int prod6k = 6 * i;
primes.add(prod6k - 1);
primes.add(prod6k + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
//remove all the factors of the numbers generated by the formula
for(int j = k * k; j <= n; j += k)//changed to k * k from 2 * k, Thanks to DTing
{
int index = primes.indexOf(j);
if(index != -1)
primes.remove(index);
}
}
System.out.println(primes);

Sin embargo, este método genera los números primos correctamente. Esto se ejecuta de una manera mucho más rápida, ya que no necesitamos verificar todos los números que verificamos en un Tamiz.

Mi pregunta es que me estoy perdiendo algún caso de borde? Esto sería mucho mejor, pero nunca vi a alguien usando esto. ¿Estoy haciendo algo mal?

¿Puede este enfoque ser mucho más optimizado?

Tomar un boolean[] lugar de un ArrayList es mucho más rápido.

int n = 100000000;
boolean[] primes = new boolean[n + 1];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
int prod6k = 6 * i;
primes[prod6k + 1] = true;
primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
for (int i = 0; i <= n; i++)
if (primes[i])
System.out.print(i + " ");

Answer 1

¿Puede este enfoque ser mucho más optimizado?

La respuesta es sí.

Comenzaré diciendo que es una buena idea usar el tamiz en un subconjunto de números dentro de un cierto rango, y su sugerencia es hacer eso exactamente.

Leyendo sobre la generación de Primes :

... Además, en función de los formalismos del tamiz, se construyen algunas secuencias de enteros (secuencia A240673 en OEIS ) que también podrían usarse para generar primos en ciertos intervalos.

El significado de este párrafo es que su enfoque de comenzar con una lista reducida de enteros fue efectivamente adoptado por la academia, pero sus técnicas son más eficientes (pero también, naturalmente, más complejas).

Answer 2

5 es el primer número generado por sus criterios. Echemos un vistazo a los números generados hasta 25:

5 , 6 7 8 , 9 , 10 11 , 12 13 14 , 15 , dieciséis 17 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25

Ahora, veamos estos mismos números, cuando usamos el algoritmo de Tamiz de Eratóstenes:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Después de quitar 2:

5 , 6 7 8 9 10 11 , 12 13 14 15 dieciséis 17 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25

Después de quitar 3:

5 , 6 7 8 , 9 , 10 11 , 12 13 14 , 15 , dieciséis 17 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25

¡Esto es lo mismo que el primer set! Note que ambos incluyen 25, lo cual no es primo. Si lo pensamos, este es un resultado obvio. Considere cualquier grupo de 6 números consecutivos:

6k - 3, 6k - 2, 6k - 1, 6k, 6k + 1, 6k + 2

Si factorizamos un poco, obtenemos:

3 * (2k - 1), 2 * (3k - 1), 6k - 1, 6 * (k), 6k + 1, 2 * (3k + 1)

En cualquier grupo de 6 números consecutivos, tres de ellos serán divisibles por dos, y dos de ellos serán divisibles por tres. ¡Estos son exactamente los números que hemos eliminado hasta ahora! Por lo tanto:

Su algoritmo para usar solo 6k - 1 y 6k + 1 es exactamente el mismo que en las dos primeras rondas del Tamiz de Erathosthenes.

También es una mejora de velocidad bastante agradable sobre el Tamiz, porque no tenemos que agregar todos esos elementos adicionales solo para eliminarlos. Esto explica por qué su algoritmo funciona y por qué no se pierde ningún caso; porque es exactamente lo mismo que el Tamiz.

De todos modos, estoy de acuerdo en que una vez que haya generado números primos, su forma boolean es, con mucho, la más rápida. He establecido un punto de referencia utilizando su forma ArrayList , su forma boolean[] y mi propia manera utilizando LinkedList e iterator.remove() (porque las eliminaciones son rápidas en una LinkedList . Aquí está el código para mi arnés de prueba. Tenga en cuenta que corro la prueba 12 veces para garantizar que la JVM se haya calentado, imprimo el tamaño de la lista y cambio el tamaño de n para intentar evitar demasiada optimización de predicción de bifurcaciones . También puede obtener más velocidad en los tres métodos usando += 6 en la semilla inicial, en lugar de prod6k :

import java.util.*;
public class PrimeGenerator {
public static List<Integer> generatePrimesArrayList(int n) {
List<Integer> primes = new ArrayList<>(getApproximateSize(n));
primes.add(2);// explicitly add
primes.add(3);// 2 and 3
for (int i = 6; i <= n; i+=6) {
// get all the numbers which can be generated by the formula
primes.add(i - 1);
primes.add(i + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
// remove all the factors of the numbers generated by the formula
for (int j = k * k; j <= n; j += k)// changed to k * k from 2 * k, Thanks
// to DTing
{
int index = primes.indexOf(j);
if (index != -1)
primes.remove(index);
}
}
return primes;
}
public static List<Integer> generatePrimesBoolean(int n) {
boolean[] primes = new boolean[n + 5];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 6; i <= n; i+=6) {
primes[i + 1] = true;
primes[i - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
int approximateSize = getApproximateSize(n);
List<Integer> primesList = new ArrayList<>(approximateSize);
for (int i = 0; i <= n; i++)
if (primes[i])
primesList.add(i);
return primesList;
}
private static int getApproximateSize(int n) {
// Prime Number Theorem. Round up
int approximateSize = (int) Math.ceil(((double) n) / (Math.log(n)));
return approximateSize;
}
public static List<Integer> generatePrimesLinkedList(int n) {
List<Integer> primes = new LinkedList<>();
primes.add(2);// explicitly add
primes.add(3);// 2 and 3
for (int i = 6; i <= n; i+=6) {
// get all the numbers which can be generated by the formula
primes.add(i - 1);
primes.add(i + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
for (Iterator<Integer> iterator = primes.iterator(); iterator.hasNext();) {
int primeCandidate = iterator.next();
if (primeCandidate == k)
continue; // Always skip yourself
if (primeCandidate == (primeCandidate / k) * k)
iterator.remove();
}
}
return primes;
}
public static void main(String... args) {
int initial = 4000;
for (int i = 0; i < 12; i++) {
int n = initial * i;
long start = System.currentTimeMillis();
List<Integer> result = generatePrimesArrayList(n);
long seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "/tArrayList Seconds: " + seconds);
start = System.currentTimeMillis();
result = generatePrimesBoolean(n);
seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "/tBoolean Seconds: " + seconds);
start = System.currentTimeMillis();
result = generatePrimesLinkedList(n);
seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "/tLinkedList Seconds: " + seconds);
}
}
}

Y los resultados de los últimos ensayos:

3432 ArrayList Seconds: 430
3432 Boolean Seconds: 0
3432 LinkedList Seconds: 90
3825 ArrayList Seconds: 538
3824 Boolean Seconds: 0
3824 LinkedList Seconds: 81
4203 ArrayList Seconds: 681
4203 Boolean Seconds: 0
4203 LinkedList Seconds: 100
4579 ArrayList Seconds: 840
4579 Boolean Seconds: 0
4579 LinkedList Seconds: 111

Answer 3

Este método a continuación muestra cómo encontrar números primos usando 6k +/- 1 lógica

Esto fue escrito en Python 3.6

def isPrime(n):
if(n<=1):
return 0
elif(n<4): #2 , 3 are prime
return 1
elif(n%2==0): #already excluded no.2 ,so any no. div. by 2 cant be prime
return 0
elif(n<9): #5, 7 are prime and 6,8 are excl. in the above step
return 1
elif(n%3==0):
return 1
f=5 #Till now we have checked the div. of n with 2,3 which means with 4,6,8 also now that is why f=5
r=int(n**.5) #rounding of root n, i.e: floor(sqrt(n)) r*r<=n
while(f<=r):
if(n%f==0): #checking if n has any primefactor lessthan sqrt(n), refer LINE 1
return 0
if(n%(f+2)==0): #remember her we are not incrementing f, see the 6k+1 rule to understand this while loop steps ,you will see that most values of f are prime
return 0
f=f+6
return 1
def prime_nos():
counter=2 #we know 2,3 are prime
print(2)
print(3) #we know 2,3 are prime
i=1
s=5 #sum 2+3
t=0
n=int(input("Enter the upper limit( should be > 3: "))
n=(n-1)//6 #finding max. limit(n=6*i+1) upto which I(here n on left hand side) should run
while(i<n):#2*(10**6)):
if (isPrime(6*i-1)):
counter=counter+1
print(6*i-1) #prime no
if(isPrime(6*i+1)):
counter=counter+1
print(6*i+1) #prime no
i+=1
prime_nos() #fn. call

Answer 4

Hay varias cosas que podrían optimizarse.

Para empezar, las operaciones "contiene" y "eliminar todo" en una ArrayList son operaciones bastante costosas (lineales para el primero, en el peor de los casos cuadrática para el segundo), por lo que es posible que no desee utilizar ArrayList para esto. A Hash- o TreeSet tiene mejores complejidades para esto, siendo casi constante (las complejidades de Hashing son extrañas) y logarítmica creo

Puede buscar en el tamiz de tamiz de Eratóstenes si desea un altogeter de tamiz más eficiente, pero eso sería además el punto de su pregunta sobre el truco 6k + -1. Es un poco más caro, pero no notablemente más costoso que su solución, pero mucho más rápido.

Answer 5

No es necesario agregar todos los posibles candidatos a la matriz. Puede crear un conjunto para almacenar todos los números primos.

También puedes comenzar a verificar en k * k , en lugar de 2 * k

 public void primesTo1000() {
Set<Integer> notPrimes = new HashSet<>();
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
for (int i = 1; i < (1000 / 6); i++) {
handlePossiblePrime(6 * i - 1, primes, notPrimes);
handlePossiblePrime(6 * i + 1, primes, notPrimes);
}
System.out.println(primes);
}
public void handlePossiblePrime(
int k, List<Integer> primes, Set<Integer> notPrimes) {
if (!notPrimes.contains(k)) {
primes.add(k);
for (int j = k * k; j <= 1000; j += k) {
notPrimes.add(j);
}
}
}

código no probado, ver esquinas

Aquí hay una versión de empacado de bits del tamiz como se sugiere en la respuesta a la que hace referencia @Will Ness . En lugar de devolver el primer _número , esta versión devuelve una lista de números primos a n:

public List<Integer> primesTo(int n) {
List<Integer> primes = new ArrayList<>();
if (n > 1) {
int limit = (n - 3) >> 1;
int[] sieve = new int[(limit >> 5) + 1];
for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {
int p = i + i + 3;
for (int j = (p * p - 3) >> 1; j <= limit; j += p)
sieve[j >> 5] |= 1 << (j & 31);
}
primes.add(2);
for (int i = 0; i <= limit; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
primes.add(i + i + 3);
}
return primes;
}

Parece que hay un error en su código actualizado que utiliza una matriz booleana (no está devolviendo todos los números primos).

public static List<Integer> booleanSieve(int n) {
boolean[] primes = new boolean[n + 5];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
int prod6k = 6 * i;
primes[prod6k + 1] = true;
primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
List<Integer> primesList = new ArrayList<>();
for (int i = 0; i <= n; i++)
if (primes[i])
primesList.add(i);
return primesList;
}
public static List<Integer> bitPacking(int n) {
List<Integer> primes = new ArrayList<>();
if (n > 1) {
int limit = (n - 3) >> 1;
int[] sieve = new int[(limit >> 5) + 1];
for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {
int p = i + i + 3;
for (int j = (p * p - 3) >> 1; j <= limit; j += p)
sieve[j >> 5] |= 1 << (j & 31);
}
primes.add(2);
for (int i = 0; i <= limit; i++)
if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
primes.add(i + i + 3);
}
return primes;
}
public static void main(String... args) {
Executor executor = Executors.newSingleThreadExecutor();
executor.execute(() -> {
for (int i = 0; i < 10; i++) {
int n = (int) Math.pow(10, i);
Stopwatch timer = Stopwatch.createUnstarted();
timer.start();
List<Integer> result = booleanSieve(n);
timer.stop();
System.out.println(result.size() + "/tBoolean: " + timer);
}
for (int i = 0; i < 10; i++) {
int n = (int) Math.pow(10, i);
Stopwatch timer = Stopwatch.createUnstarted();
timer.start();
List<Integer> result = bitPacking(n);
timer.stop();
System.out.println(result.size() + "/tBitPacking: " + timer);
}
});
}

0 Boolean: 38.51 μs
4 Boolean: 45.77 μs
25 Boolean: 31.56 μs
168 Boolean: 227.1 μs
1229 Boolean: 1.395 ms
9592 Boolean: 4.289 ms
78491 Boolean: 25.96 ms
664116 Boolean: 133.5 ms
5717622 Boolean: 3.216 s
46707218 Boolean: 32.18 s
0 BitPacking: 117.0 μs
4 BitPacking: 11.25 μs
25 BitPacking: 11.53 μs
168 BitPacking: 70.03 μs
1229 BitPacking: 471.8 μs
9592 BitPacking: 3.701 ms
78498 BitPacking: 9.651 ms
664579 BitPacking: 43.43 ms
5761455 BitPacking: 1.483 s
50847534 BitPacking: 17.71 s

Answer 6

Probablemente la estructura de datos estándar más adecuada para el Tamiz de Eratóstenes es el BitSet . Aquí está mi solución:

static BitSet genPrimes(int n) {
BitSet primes = new BitSet(n);
primes.set(2); // add 2 explicitly
primes.set(3); // add 3 explicitly
for (int i = 6; i <= n ; i += 6) { // step by 6 instead of multiplication
primes.set(i - 1);
primes.set(i + 1);
}
int max = (int) Math.sqrt(n); // don''t need to filter multiples of primes bigger than max
// this for loop enumerates all set bits starting from 5 till the max
// sieving 2 and 3 is meaningless: n*6+1 and n*6-1 are never divisible by 2 or 3
for (int i = primes.nextSetBit(5); i >= 0 && i <= max; i = primes.nextSetBit(i+1)) {
// The actual sieve algorithm like in your code
for(int j = i * i; j <= n; j += i)
primes.clear(j);
}
return primes;
}

Uso:

BitSet primes = genPrimes(1000); // generate primes up to 1000
System.out.println(primes.cardinality()); // print number of primes
// print all primes like {2, 3, 5, ...}
System.out.println(primes);
// print all primes one per line
for(int prime = primes.nextSetBit(0); prime >= 0; prime = primes.nextSetBit(prime+1))
System.out.println(prime);
// print all primes one per line using java 8:
primes.stream().forEach(System.out::println);

La versión booleana puede funcionar más rápido para valores de n pequeños, pero si necesita, por ejemplo, un millón de números primos, BitSet lo superará varias veces y realmente funcionará correctamente. Aquí está el punto de referencia cojo:

public static void main(String... args) {
long start = System.nanoTime();
BitSet res = genPrimes(10000000);
long diff = System.nanoTime() - start;
System.out.println(res.cardinality() + "/tBitSet Seconds: " + diff / 1e9);
start = System.nanoTime();
List<Integer> result = generatePrimesBoolean(10000000); // from durron597 answer
diff = System.nanoTime() - start;
System.out.println(result.size() + "/tBoolean Seconds: " + diff / 1e9);
}

Salida:

664579 BitSet Seconds: 0.065987717
664116 Boolean Seconds: 0.167620323

664579 es el número correcto de números primos por debajo de 10000000.

Answer 7

Puedes generar tus números de prueba con una rueda, sumando 2 y 4 alternativamente, lo que elimina la multiplicación en 6 * k +/- 1.

public void primesTo1000() {
Set<Integer> notPrimes = new HashSet<>();
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2); //explicitly add
primes.add(3); //2 and 3
int step = 2;
int num = 5 // 2 and 3 already handled.
while (num < 1000) {
handlePossiblePrime(num, primes, notPrimes);
num += step; // Step to next number.
step = 6 - step; // Step by 2, 4 alternately.
}
System.out.println(primes);
}