prime factor java performance algorithm primes

factor - ¿Cuál sería el método más rápido para probar la primalidad en Java?



prime factor algorithm (13)

Aquí hay otra forma:

boolean isPrime(long n) { if(n < 2) return false; if(n == 2 || n == 3) return true; if(n%2 == 0 || n%3 == 0) return false; long sqrtN = (long)Math.sqrt(n)+1; for(long i = 6L; i <= sqrtN; i += 6) { if(n%(i-1) == 0 || n%(i+1) == 0) return false; } return true; }

y BigInteger''s isProbablePrime(...) es válido para todos los 32 bits int .

EDITAR

Tenga en cuenta que isProbablePrime(certainty) no siempre produce la respuesta correcta. Cuando la certeza es baja, produce falsos positivos, como @dimo414 mencionado en los comentarios.

Lamentablemente, no pude encontrar la fuente que afirmaba que es isProbablePrime(certainty) es válida para todos los int (32 bits) (¡con la certeza suficiente!).

Entonces realicé un par de pruebas. BitSet un BitSet de tamaño Integer.MAX_VALUE/2 representaba todos los números desiguales y usé un tamiz principal para encontrar todos los números primos en el rango 1..Integer.MAX_VALUE . Luego hice un bucle desde i=1..Integer.MAX_VALUE para probar que cada new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i) .

Para certeza 5 y 10, isProbablePrime(...) produjo falsos positivos a lo largo de la línea. Pero con isProbablePrime(15) , ninguna prueba falló.

Aquí está mi plataforma de prueba:

import java.math.BigInteger; import java.util.BitSet; public class Main { static BitSet primes; static boolean isPrime(int p) { return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2))); } static void generatePrimesUpTo(int n) { primes = new BitSet(n/2); for(int i = 0; i < primes.size(); i++) { primes.set(i, true); } primes.set(0, false); int stop = (int)Math.sqrt(n) + 1; int percentageDone = 0, previousPercentageDone = 0; System.out.println("generating primes..."); long start = System.currentTimeMillis(); for(int i = 0; i <= stop; i++) { previousPercentageDone = percentageDone; percentageDone = (int)((i + 1.0) / (stop / 100.0)); if(percentageDone <= 100 && percentageDone != previousPercentageDone) { System.out.println(percentageDone + "%"); } if(primes.get(i)) { int number = (i * 2) + 1; for(int p = number * 2; p < n; p += number) { if(p < 0) break; // overflow if(p%2 == 0) continue; primes.set(p/2, false); } } } long elapsed = System.currentTimeMillis() - start; System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds"); } private static void test(final int certainty, final int n) { int percentageDone = 0, previousPercentageDone = 0; long start = System.currentTimeMillis(); System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n); for(int i = 1; i < n; i++) { previousPercentageDone = percentageDone; percentageDone = (int)((i + 1.0) / (n / 100.0)); if(percentageDone <= 100 && percentageDone != previousPercentageDone) { System.out.println(percentageDone + "%"); } BigInteger bigInt = new BigInteger(String.valueOf(i)); boolean bigIntSays = bigInt.isProbablePrime(certainty); if(isPrime(i) != bigIntSays) { System.out.println("ERROR: isProbablePrime(" + certainty + ") returns " + bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn''t" ) + " a prime"); return; } } long elapsed = System.currentTimeMillis() - start; System.out.println("finished testing in ~" + ((elapsed/1000)/60) + " minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")"); } public static void main(String[] args) { int certainty = Integer.parseInt(args[0]); int n = Integer.MAX_VALUE; generatePrimesUpTo(n); test(certainty, n); } }

que ejecuté haciendo:

java -Xmx1024m -cp . Main 15

La generación de los primos tomó ~ 30 segundos en mi máquina. Y la prueba real de todo i en 1..Integer.MAX_VALUE tomó alrededor de 2 horas y 15 minutos.

Estoy tratando de encontrar la manera más rápida de verificar si un número dado es primo o no (en Java). A continuación se muestran varios métodos de prueba de primalidad que se me ocurrieron. ¿Hay alguna forma mejor que la segunda implementación (isPrime2)?

public class Prime { public static boolean isPrime1(int n) { if (n <= 1) { return false; } if (n == 2) { return true; } for (int i = 2; i <= Math.sqrt(n) + 1; i++) { if (n % i == 0) { return false; } } return true; } public static boolean isPrime2(int n) { if (n <= 1) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) { if (n % i == 0) { return false; } } return true; } } public class PrimeTest { public PrimeTest() { } @Test public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException { Prime prime = new Prime(); TreeMap<Long, String> methodMap = new TreeMap<Long, String>(); for (Method method : Prime.class.getDeclaredMethods()) { long startTime = System.currentTimeMillis(); int primeCount = 0; for (int i = 0; i < 1000000; i++) { if ((Boolean) method.invoke(prime, i)) { primeCount++; } } long endTime = System.currentTimeMillis(); Assert.assertEquals(method.getName() + " failed ", 78498, primeCount); methodMap.put(endTime - startTime, method.getName()); } for (Entry<Long, String> entry : methodMap.entrySet()) { System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds "); } } }

Creo que este método es el mejor. al menos para mi-

public static boolean isPrime(int num) { for (int i = 2; i<= num/i; i++) { if (num % i == 0) { return false; } } return num > 1; }

Dependiendo de la longitud del número que necesita probar, puede precomputar una lista de números primos para valores pequeños (n <10 ^ 6), que se usa primero, si el número solicitado se encuentra dentro de este rango. Esta es, por supuesto, la forma más rápida. Como se menciona en otras respuestas, el tamiz de Eratóstenes es el método preferido para generar dicha lista precalculada.

Si sus números son más grandes que esto, puede usar la prueba de primalidad de Rabin. Prueba de primalidad Rabin

Dio el primer paso para eliminar todos los múltiplos de 2.

Sin embargo, ¿por qué te detuviste allí? podrías haber eliminado todos los múltiplos de 3 excepto 3, todos los múltiplos de 5 excepto 5, etc.

Cuando sigas este razonamiento hasta su conclusión, obtendrás el Tamiz de Eratóstenes .

Esta es la manera más elegante:

public static boolean isPrime(int n) { return !new String(new char[n]).matches(".?|(..+?)//1+"); }

Java 1.4+. No se necesitan importaciones

Tan corto. Tan hermosa.

Lo que ha escrito es lo que hacen los programadores más comunes y que debería ser suficiente la mayor parte del tiempo.

Sin embargo, si busca el "mejor algoritmo científico", hay muchas variaciones (con distintos niveles de certidumbre) documentadas en http://en.wikipedia.org/wiki/Prime_number .

Por ejemplo, si tiene un número de 70 dígitos, las limitaciones físicas de JVM pueden impedir que su código se ejecute, en cuyo caso puede usar "Sieves", etc.

De nuevo, como dije si esta era una pregunta de programación o una pregunta general sobre el uso en el software, tu código debería ser perfecto :)

Optimicé la división de prueba aquí: devuelve un booleano. Los métodos distintos de isPrime (n) también son necesarios.

static boolean[] smlprime = {false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false}; public static boolean isPrime(long n) { //optimised if (n < 2) { return false; } if (n < smlprime.length) //less than smlprime.length do not need to be checked { return smlprime[(int) n]; //lol already checked } long[] dgt = longDigits(n); long ones = dgt[dgt.length - 1]; if (ones % 2 == 0) { return false; } if (ones == 0 || ones == 5) { return false; } if (digitadd(n) % 3 == 0) { return false; } if (n % 7 == 0) { return false; } if (Square(n)) { return false; } long hf = (long) Math.sqrt(n); for (long j = 11; j < hf; j = nextProbablePrime(j)) { //System.out.prlongln(Math.sqrt(i)); if (n % j == 0) { return false; } //System.out.prlongln("res"+res); } return true; } public static long nextProbablePrime(long n) { for (long i = n;; i++) { if (i % 2 != 0 && i % 3 != 0 && i % 7 != 0) { return i; } } } public static boolean Square(long n) { long root = (long) Math.sqrt(n); return root * root == n; } public static long[] longDigits(long n) { String[] a = Long.toString(n).split("(?!^)"); long[] out = new long[a.length]; for (int i = 0; i < a.length; i++) { out[i] = Long.parseLong(a[i]); } return out; } public static long digitadd(long n) { long[] dgts = longDigits(n); long ans = 0; for (long i : dgts) { ans += i; } return ans; }

Por supuesto, hay cientos de pruebas de primalidad, todas con diversas ventajas y desventajas basadas en el tamaño del número, las formas especiales, el tamaño del factor, etc.

Sin embargo, en Java encuentro el más útil para ser esto:

BigInteger.valueOf(long/int num).isProbablePrime(int certainty);

Ya está implementado, y es bastante rápido (considero que lleva ~ 6 segundos para una matriz de 1000x1000 llena de longs 0-2 ^ 64 y una certeza de 15) y probablemente sea mejor optimizado que cualquier cosa que los mortales pudiéramos obtener.

Utiliza una versión de la prueba de primalidad Baillie-PSW , que no tiene contraejemplos conocidos. (aunque podría usar una versión ligeramente más débil de la prueba, que a veces puede ser errónea)

Si solo estás tratando de encontrar si un número es primo o no, es lo suficientemente bueno, pero si estás tratando de encontrar todos los números primos de 0 a na, la mejor opción será el Tamiz de Eratóstenes.

Pero dependerá de las limitaciones de Java en los tamaños de matriz, etc.

Su algoritmo funcionará bien para números razonablemente pequeños. Para números grandes, se deben usar algoritmos avanzados (basados, por ejemplo, en curvas elípticas). Otra idea será usar alguna prueba de "pseuso-primes". Estos probarán rápidamente que un número es primo, pero no son 100% precisos. Sin embargo, pueden ayudarlo a descartar algunos números más rápido que con su algoritmo.

Finalmente, aunque el compilador probablemente optimizará esto para usted, debe escribir:

int max = (int) (Math.sqrt(n) + 1); for (int i = 3; i <= max; i = i + 2) { }

Una prueba rápida debido a Jaeschke (1993) es una versión determinística de la prueba Miller-Rabin, que no tiene falsos positivos por debajo de 4.759,123,141 y, por lo tanto, se puede aplicar a Java int s.

// Given a positive number n, find the largest number m such // that 2^m divides n. private static int val2(int n) { int m = 0; if ((n&0xffff) == 0) { n >>= 16; m += 16; } if ((n&0xff) == 0) { n >>= 8; m += 8; } if ((n&0xf) == 0) { n >>= 4; m += 4; } if ((n&0x3) == 0) { n >>= 2; m += 2; } if (n > 1) { m++ } return m; } // For convenience, handle modular exponentiation via BigInteger. private static int modPow(int base, int exponent, int m) { BigInteger bigB = BigInteger.valueOf(base); BigInteger bigE = BigInteger.valueOf(exponent); BigInteger bigM = BigInteger.valueOf(m); BigInteger bigR = bigB.modPow(bigE, bigM); return bigR.intValue(); } // Basic implementation. private static boolean isStrongProbablePrime(int n, int base) { int s = val2(n-1); int d = modPow(b, n>>s, n); if (d == 1) { return true; } for (int i=1; i < s; i++) { if (d+1 == n) { return true; } d = d*d % n; } return d+1 == n; } public static boolean isPrime(int n) { if ((n&1) == 0) { return n == 2; } if (n < 9) { return n > 1; } return isStrongProbablePrime(n, 2) && isStrongProbablePrime(n, 7) && isStrongProbablePrime(n, 61); }

Esto no funciona para variables long , pero sí una prueba diferente: la prueba BPSW no tiene contraejemplos hasta 2 ^ 64. Básicamente, esto consiste en una prueba de probabilidad probable de 2 puntos fuertes como la anterior, seguida de una prueba fuerte de Lucas que es un poco más complicada pero no fundamentalmente diferente.

Ambas pruebas son mucho más rápidas que cualquier tipo de división de prueba.

Eficiencia del algoritmo: O (n ^ (1/2)) Algoritmo

Nota: Este código de muestra a continuación contiene variables de recuento y llamadas a una función de impresión con el objetivo de imprimir los resultados:

import java.util.*; class Primality{ private static void printStats(int count, int n, boolean isPrime) { System.err.println( "Performed " + count + " checks, determined " + n + ( (isPrime) ? " is PRIME." : " is NOT PRIME." ) ); } /** * Improved O( n^(1/2)) ) Algorithm * Checks if n is divisible by 2 or any odd number from 3 to sqrt(n). * The only way to improve on this is to check if n is divisible by * all KNOWN PRIMES from 2 to sqrt(n). * * @param n An integer to be checked for primality. * @return true if n is prime, false if n is not prime. **/ public static boolean primeBest(int n){ int count = 0; // check lower boundaries on primality if( n == 2 ){ printStats(++count, n, true); return true; } // 1 is not prime, even numbers > 2 are not prime else if( n == 1 || (n & 1) == 0){ printStats(++count, n, false); return false; } double sqrtN = Math.sqrt(n); // Check for primality using odd numbers from 3 to sqrt(n) for(int i = 3; i <= sqrtN; i += 2){ count++; // n is not prime if it is evenly divisible by some ''i'' in this range if( n % i == 0 ){ printStats(++count, n, false); return false; } } // n is prime printStats(++count, n, true); return true; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNext()) { int n = scan.nextInt(); primeBest(n); System.out.println(); } scan.close(); } }

Cuando se ingresa el número primo 2147483647, produce el siguiente resultado:

Se realizaron 23170 comprobaciones, se determinó que 2147483647 es PRIME.