Quelle serait la méthode la plus rapide pour tester la primalité en Java?

Question

J'essaie de trouver le moyen le plus rapide de vérifier si un nombre donné est premier ou non (en Java). Voici plusieurs méthodes de test de primalité que j'ai trouvées. Existe-t-il un meilleur moyen que la deuxième implémentation (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 ");
        }
    }
}
 

Answer 1

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 l'ensemble des 32 bits ints'.

MODIFIER

Notez que isProbablePrime(certainty) ne produit pas toujours de la bonne réponse. Lorsque la certitude est sur le bas côté, il produit des faux positifs, comme @dimo414 mentionné dans les commentaires.

Malheureusement, je ne pouvais pas trouver la source qui a coûté isProbablePrime(certainty) est valable pour tous (32 bits) ints '(donné assez de certitude!).

J'ai donc effectué quelques tests. J'ai créé un BitSet de la taille de l' Integer.MAX_VALUE/2 représentant tous les impairs et utilisé un premier tamis pour trouver tous les nombres premiers dans la gamme 1..Integer.MAX_VALUE. Je puis en boucle à partir d' i=1..Integer.MAX_VALUE de vérifier que chaque new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i).

Pour la certitude de 5 et de 10, isProbablePrime(...) produit des faux positifs, le long de la ligne. Mais avec isProbablePrime(15), pas de 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);
    }
}

qui j'ai couru en faisant:

java -Xmx1024m -cp . Main 15

La génération des nombres premiers a pris ~30 sec sur ma machine. Et le test de tous les i en 1..Integer.MAX_VALUE a fallu environ 2 heures et 15 minutes.

Answer 2

C'est la manière 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.

Si court. Si belle.

Answer 3

Jetez un œil au test de primalité AKS (et ses différentes optimisations). Il s'agit d'un test de primalité déterministe qui s'exécute en temps polynomial.

Il y a une implémentation de l'algorithme en java ici

Answer 4

Vous avez fait le premier pas pour éliminer tous les pouvoirs de 2.

Mais pourquoi vous êtes-vous arrêté là? vous auriez pu éliminer tous les pouvoirs de 3 sauf 3, tous les pouvoirs de 5 sauf 5, etc.

Lorsque vous suivez ce raisonnement jusqu'à sa conclusion, vous obtenez le tamis d'Ératosthène .

Answer 5

Votre algorithme fonctionne bien pour raisonnablement petit nombre. Pour les grands nombres, les algorithmes avancés devrait être utilisé (basée par exemple sur les courbes elliptiques). Une autre idée est d'utiliser certains "pseuso-nombres premiers" de test. Ces permettra de tester rapidement qu'un nombre est un nombre premier, mais ils ne sont pas précis à 100%. Cependant, ils peuvent vous aider à quelques numéros plus vite que votre algorithme.

Enfin, bien que le compilateur va probablement optimiser pour vous, vous devez écrire:

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