Méthode Arcane isPrime en Java

Question

Considérez la méthode suivante :

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

Je n'ai jamais été un gourou des expressions régulières, alors quelqu'un peut-il m'expliquer comment cette méthode fonctionne réellement ? En outre, Cette méthode est efficace par rapport aux autres méthodes possibles pour déterminer si un nombre entier est premier.

Answer 1

Tout d'abord, notez que cette regex s'applique aux nombres représentés dans un système de comptage unaire, à savoir

1       is 1
11      is 2
111     is 3
1111    is 4
11111   is 5
111111  is 6
1111111 is 7

et ainsi de suite. En fait, n'importe quel caractère peut être utilisé (d'où l'appellation de "caractère"). . dans l'expression), mais je vais utiliser "1".

Deuxièmement, notez que cette regex correspond à composite (non primaires) ; la négation détecte donc la primalité.

---

Explication :

La première moitié de l'expression,

.?

dit que les chaînes "" (0) et "1" (1) sont des correspondances, c'est-à-dire qu'il n'est pas premier (par définition, bien que discutable .)

La seconde moitié, en anglais simple, dit :

Faites correspondre la chaîne la plus courte dont la longueur est au moins égale à 2, par exemple, "11" (2). Maintenant, voyons si nous pouvons faire correspondre la chaîne entière en la répétant. Est-ce que "1111" (4) correspond ? Est-ce que "111111" (6) correspond ? Est-ce que "11111111" (8) correspond ? Et ainsi de suite. Si ce n'est pas le cas, essayez à nouveau avec la chaîne la plus courte suivante, "111" (3). Etc.

Vous pouvez maintenant voir comment, si la chaîne de caractères originale ne peut pas être appariée comme un multiple de ses sous-chaînes, alors par définition, il est premier !

D'ailleurs, l'opérateur non avide ? est ce qui fait que l'"algorithme" commence par le plus court et compte vers le haut.

---

Efficacité :

C'est intéressant, mais certainement pas efficace, selon divers arguments, dont certains que je vais regrouper ci-dessous :

• Comme le note @TeddHopp, l'approche bien connue du tamis d'Eratosthène ne prendrait pas la peine de vérifier les multiples d'entiers tels que 4, 6 et 9, ayant déjà été "visités" lors de la vérification des multiples de 2 et 3. Hélas, cette approche par regex vérifie de manière exhaustive tous les petits entiers.

• Comme le note @PetarMinchev, nous pouvons "court-circuiter" le schéma de vérification des multiples dès que nous atteignons la racine carrée du nombre. Nous devrions être en mesure de car un facteur plus grand que la racine carrée doit s'associer à un facteur moins que la racine carrée (car autrement, deux facteurs supérieurs à la racine carrée donneraient un produit supérieur au nombre), et si ce facteur supérieur existe, alors nous devrions déjà avoir rencontré (et donc correspondre) le facteur inférieur.

• Comme @Jesper et @Brian le notent avec concision, d'un point de vue non-algorithmique, considérez comment une expression régulière commencerait par allouer de la mémoire pour stocker la chaîne de caractères , par exemple char[9000] pour 9000. Eh bien, c'était facile, n'est-ce pas ? ;)

• Comme le note @Foon, il existe des méthodes probabilistes qui peuvent être plus efficaces pour les grands nombres, bien qu'elles ne soient pas toujours correctes (elles peuvent donner des pseudo-primes). Mais il existe aussi des tests déterministes qui sont exacts à 100% et bien plus efficaces que les méthodes basées sur le tamis. Wolfram's a un bon résumé.

Answer 2

Les caractéristiques unaires des nombres premiers et la raison pour laquelle cela fonctionne ont déjà été abordées. Voici donc un test utilisant les approches conventionnelles et cette approche :

public class Main {

    public static void main(String[] args) {
        long time = System.nanoTime();
        for (int i = 2; i < 10000; i++) {
            isPrimeOld(i);
        }
        time = System.nanoTime() - time;
        System.out.println(time + " ns (" + time / 1000000 + " ms)");
        time = System.nanoTime();
        for (int i = 2; i < 10000; i++) {
            isPrimeRegex(i);
        }
        time = System.nanoTime() - time;
        System.out.println(time + " ns (" + time / 1000000 + " ms)");
        System.out.println("Done");
    }

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

    public static boolean isPrimeOld(int n) {
        if (n == 2)
            return true;
        if (n < 2)
            return false;
        if ((n & 1) == 0)
            return false;
        int limit = (int) Math.round(Math.sqrt(n));
        for (int i = 3; i <= limit; i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}

Ce test calcule si le nombre est premier ou non jusqu'à 9 999, en partant de 2. Et voici son résultat sur un serveur relativement puissant :

8537795 ns (8 ms)
30842526146 ns (30842 ms)
Done

C'est donc très inefficace une fois que les nombres deviennent suffisamment grands. (Jusqu'à 999, la regex s'exécute en 400 ms environ). Pour les petits nombres, c'est rapide, mais il est toujours plus rapide de générer les nombres premiers jusqu'à 9 999 de manière conventionnelle que de générer les nombres premiers jusqu'à 99 de manière traditionnelle (23 ms).

Answer 3

Ce n'est pas un moyen vraiment efficace de vérifier si un nombre est premier (il vérifie chaque diviseur).

Une manière efficace est de vérifier les diviseurs jusqu'à sqrt(number) . C'est le cas si vous voulez être certain qu'un nombre est premier. Sinon, il existe des contrôles de primalité probabilistes qui sont plus rapides, mais pas 100% corrects.