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);
}