Quelle serait la méthode la plus rapide pour tester la primalité en Java?
https://stackoverflow.com/questions/2385909
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis en train de trouver le meilleur moyen de vérifier si un nombre est premier ou non (en Java). Voici plusieurs méthodes de test de primalité Je suis arrivé avec. Y at-il de mieux que la deuxième mise en œuvre (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 ");
}
}
}
La solution
Voici une autre façon:
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;
}
et BigInteger's isProbablePrime(...) est valable pour tous les bits de 32 de int.
EDIT
Notez que isProbablePrime(certainty) ne produit pas toujours la bonne réponse. Lorsque la certitude est du côté basse, il produit des faux positifs, comme @ dimo414 mentionné dans les commentaires.
Malheureusement, je ne pouvais pas trouver la source qui a fait isProbablePrime(certainty) est valable pour tous (32 bits) de int (assez de certitude donnée!).
J'effectué quelques tests. J'ai créé un BitSet de taille Integer.MAX_VALUE/2 représentant tous les nombres impairs et utilisé un tamis premier pour trouver tous les nombres premiers dans la gamme 1..Integer.MAX_VALUE. Je me suis alors mis en boucle de i=1..Integer.MAX_VALUE pour vérifier que tous les new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i).
Pour la sécurité 5 et 10, isProbablePrime(...) produit faux positifs le long de la ligne. Mais avec isProbablePrime(15), aucun test a échoué.
Voici mon banc d'essai:
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 je courais en faisant:
java -Xmx1024m -cp . Main 15
La génération des nombres premiers a ~ 30 sec sur ma machine. Et le test réel de tous i en 1..Integer.MAX_VALUE a pris environ 2 heures et 15 minutes.
Autres conseils
Ceci est la façon la plus élégante:
public static boolean isPrime(int n) {
return !new String(new char[n]).matches(".?|(..+?)\\1+");
}
Java 1.4+. Aucune importation nécessaire.
court. Si beau.
Jetez un oeil à la AKS primalité de test (et ses diverses optimisations). Il est un test de primalité déterministe qui fonctionne en temps polynomial.
Il y a une implémentation de l'algorithme en Java de l'Université de Tuebingen (Allemagne)
Vous avez pris la première étape dans l'élimination de tous les multiples de 2.
Cependant, pourquoi avez-vous arrêter là? vous pourriez avoir éliminé tous les multiples de 3, sauf pour 3, tous les multiples de 5, sauf pour 5, etc.
Lorsque vous suivez ce raisonnement à sa conclusion, vous obtenez le Sieve de Eratosthène.
Votre algorithme fonctionne bien pour un nombre relativement petits. Pour les grands nombres, des algorithmes avancés devraient être utilisés (par exemple à base de courbes elliptiques). Une autre idée sera d'utiliser un test « pseuso-nombres premiers ». Ceux-ci tester rapidement qu'un nombre est un nombre premier, mais ils ne sont pas précis à 100%. Cependant, ils peuvent vous aider à écarter quelques chiffres plus rapidement que votre algorithme.
Enfin, bien que le compilateur optimisera probablement pour vous, vous devez écrire:
int max = (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}
Qu'est-ce que vous avez écrit est ce que les programmeurs les plus courants font et qui devrait être suffisant la plupart du temps.
Cependant, si vous êtes après le « meilleur algorithme scientifique », il existe de nombreuses variantes (avec différents niveaux de sécurité) documentés http://en.wikipedia.org/wiki/Prime_number .
Par exemple, si vous avez un numéro de 70 chiffres limites physiques de JVM peut empêcher votre code de courir dans ce cas, vous pouvez utiliser des « passoires » etc.
Encore une fois, comme je l'ai dit si cela était une question de programmation ou d'une question générale d'utilisation dans le logiciel de votre code doit être parfait:)
En fonction de la longueur du numéro que vous devez vous tester pouvez précalculer une liste de nombres premiers pour les petites valeurs (n <10 ^ 6), qui est utilisé en premier lieu, si le nombre demandé est dans cette plage. Ceci est bien sûr le moyen le plus rapide. Comme mentionné dans d'autres réponses Crible d'Ératosthène est la méthode préférée pour générer une telle liste précalculée.
Si vos chiffres sont plus grandes que cela, vous pouvez utiliser le test de primalité de Rabin. test Rabin primalité
Je pense que cette méthode est la meilleure. au moins pour moi -
public static boolean isPrime(int num)
{
for (int i = 2; i<= num/i; i++)
{
if (num % i == 0)
{
return false;
}
}
return num > 1;
}
Un test rapide en raison de Jaeschke (1993) est une version déterministe du test de Miller-Rabin, qui n'a pas de faux positifs ci-dessous 4759123141 et peut donc être appliqué à Java ints.
// 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);
}
Cela ne fonctionne pas pour les variables long, mais un fait test différent: le test BPSW n'a pas jusqu'à 2 contre-^ 64. Il est composé essentiellement d'un test d'amorçage probable 2-fort comme ci-dessus suivi d'un solide test de Lucas qui est un peu plus compliqué, mais pas fondamentalement différent.
Ces deux tests sont beaucoup plus rapidement que toute sorte de division de première instance.
Il y a bien sûr des centaines de tests de primalité, tous avec différents avantages et inconvénients en fonction de la taille du nombre, des formulaires spéciaux, la taille des facteurs, etc.
Cependant, en java je trouve le plus utile de ceci:
BigInteger.valueOf(long/int num).isProbablePrime(int certainty);
Son déjà mis en œuvre, et est assez rapide (je trouve qu'il faut ~ 6 secondes pour une matrice de 1000x1000 rempli de positions longues 0-2 ^ 64 et une certitude de 15) et probablement mieux optimisé que tout ce que nous les mortels pourraient trouver.
Il utilise une version du Baillie-PSW test de primalité , qui n'a pas de contre-savoir. (Bien qu'il pourrait utiliser une version légèrement plus faible de l'essai, ce qui peut parfois se tromper. Peut-être)
Je ici la division optimisé d'essai: elle renvoie une valeur booléenne. Les méthodes autres que isPrime (n) sont également nécessaires.
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;
}
Efficacité Algorithme: O (n ^ (1/2)) Algorithme
Note: Ce code exemple ci-dessous contient des variables de comptage et appelle à une fonction d'impression aux fins d'impression des résultats:
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();
}
}
Lorsque le nombre premier 2147483647 est entré, il produit la sortie suivante:
Joué 23170 chèques, déterminée 2147483647 est PRIME.
testé dans un Intel Atom @ 1.60GHz, 2 Go de RAM, 32 bits du système d'exploitation
Résultat du test:
le plus grand nombre premier ci-dessous Long.MAX_VALUE = 9223372036854775807 est 9223372036854775783
le temps écoulé est 171499 millisecondes ou 2 minutes et 51 secondes
public class PrimalityTest
{
public static void main(String[] args)
{
long current_local_time = System.currentTimeMillis();
long long_number = 9223372036854775783L;
long long_a;
long long_b;
if (long_number < 2)
{
System.out.println(long_number + " is not a prime number");
}
else if (long_number < 4)
{
System.out.println(long_number + " is a prime number");
}
else if (long_number % 2 == 0)
{
System.out.println(long_number + " is not a prime number and is divisible by 2");
}
else
{
long_a = (long) (Math.ceil(Math.sqrt(long_number)));
terminate_loop:
{
for (long_b = 3; long_b <= long_a; long_b += 2)
{
if (long_number % long_b == 0)
{
System.out.println(long_number + " is not a prime number and is divisible by " + long_b);
break terminate_loop;
}
}
System.out.println(long_number + " is a prime number");
}
}
System.out.println("elapsed time: " + (System.currentTimeMillis() - current_local_time) + " millisecond/s");
}
}
