Comment déterminer si un nombre est un nombre premier avec regex?

Question

J'ai trouvé l'exemple de code suivant pour Java sur RosettaCode :

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

• Je ne connais pas Java en particulier, mais je comprends tous les aspects de cet extrait, à l'exception du regex lui-même.
• J'ai une connaissance de base à avancée de Regex telle que vous la trouverez dans les fonctions PHP intégrées

Comment .?|(..+?)\\1+ correspond-il aux nombres premiers?

Answer 1

Vous avez dit que vous comprendre cette partie, mais juste pour souligner, la Chaîne a généré une longueur égale au nombre fourni. Ainsi, la chaîne a trois caractères si et seulement si n == 3.

.?

La première partie de la regex dit, "n'importe quel caractère, zéro ou une fois". Donc, fondamentalement, il est zéro ou un caractère, ou, par ce que j'ai mentionné ci-dessus, n == 0 || n == 1. Si nous avons le match, puis retourner la négation. Ceci correspond au fait que le zéro et l'un ne sont PAS le premier.

(..+?)\\1+

La deuxième partie de l'expression régulière est un peu plus délicat, en s'appuyant sur les groupes et les références arrières. Un groupe est quelque chose entre parenthèses, qui seront ensuite recueillies et stockées par le moteur d'expressions régulières pour les utiliser plus tard. Une référence arrière est un groupe apparié, qui est ensuite utilisé dans le même regex.

Le groupe de capture 1 caractère, puis 1 ou plus de n'importe quel caractère. (Le caractère + signifie un ou plusieurs, mais SEULEMENT du caractère précédent ou d'un groupe. Ce n'est donc pas "deux, quatre ou six, etc. des personnages", mais plutôt "deux ou trois etc." Le +? c'est comme +, mais il essaie de faire correspondre aussi peu de caractères que possible. + normalement essaie d'avaler de l'ensemble de la chaîne si elle peut, ce qui est mauvais dans ce cas, car il empêche la référence arrière de la partie de travail.)

La partie suivante est la référence arrière: le même jeu de caractères (deux ou plus), apparaissant de nouveau. Dit backreference apparaît une ou plusieurs fois.

. Le groupe capturé correspond à un nombre de caractères (à partir de 2 ensuite) capturé. Dit groupe apparaît alors naturellement d'un certain nombre de fois (également à partir de 2 ensuite). Si il y a un match, ce qui implique qu'il est possible de trouver un produit de deux nombres est supérieur ou égal à 2 qui correspond à la n de chaîne de longueur... ce qui signifie que vous avez un composite n. Encore une fois, de retour de la négation de la correspondance: n n'est PAS premier.

Si aucune correspondance n'est trouvée, vous ne pouvez pas venir avec votre produit de deux nombres naturels supérieurs ou égaux à 2... et vous avez à la fois un non-match et un premier, d'où encore une fois le retour de la négation du résultat du match.

Voyez-vous maintenant? C'est incroyablement difficile (et coûteux en termes de calcul!) mais c'est aussi un peu simple, dans le même temps, une fois que vous l'obtenez. :-)

Je peux élaborer si vous avez d'autres questions, comme sur la façon regex l'analyse fonctionne réellement. Mais je vais essayer de garder cette réponse simple pour l'instant (ou aussi simple que cela peut être jamais).

Answer 2

Je vais vous expliquer les regex en dehors de test de primalité: la regex suivante, compte tenu d'un String s qui consiste à répéter String t, conclut t.

    System.out.println(
        "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1")
    ); // prints "Mamamia"

La façon dont cela fonctionne est que la regex capture (.*) en \1, et voit si il y a \1+ suivant. À l'aide de l' ^ et $ assure qu'un match doit être de l'ensemble de la chaîne.

Donc dans un sens, nous sommes donnée, String s, ce qui est un "multiple" de String t, et la regex trouverez par exemple t (la plus longue possible, depuis \1 est gourmand).

Une fois que vous comprenez pourquoi cette regex fonctionne, alors (en ignorant le premier suppléant dans l'OP de la regex pour l'instant) en expliquant comment il est utilisé pour les tests de primalité est simple.

• Pour tester la primalité d' n, d'abord générer un String de la longueur n (rempli avec le même char)
• La regex de capture d'un String d'une certaine longueur (disons k) en \1, et tente de faire correspondre \1+ pour le reste de l' String
  • Si il y a un match, alors n est un multiple de k, et, par conséquent, n n'est pas premier.
  • Si il n'y a pas de match, cette k existe qui divise n, et n est donc un premier

---

Comment est - .?|(..+?)\1+ correspondent à des nombres premiers?

En fait, il n'est pas! Il correspond String dont la longueur n'est PAS premier!

• .? : La première partie de l'alternance correspond String de la longueur 0 ou 1 (PAS le premier, par définition)
• (..+?)\1+ : La deuxième partie de l'alternance, une variation de l'expression rationnelle expliqué ci-dessus, correspond à, String de la longueur n qui est "multiple" de String de la longueur k >= 2 (c - n est un composite, PAS premier).
  • Notez que les réticents modificateur ? est en fait pas nécessaire pour la correction, mais il peut aider à accélérer le processus en essayant de petits k premier

Remarque l' ! boolean opérateur de complément dans l' return déclaration: il nie l' matches. C'est quand la regex N'a PAS de match, n est le premier! C'est un double négatif de la logique, donc pas étonnant que c'est un peu déroutant!!

---

La Simplification

Voici une simple réécriture du code pour le rendre plus lisible:

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

Le ci-dessus est essentiellement le même que l'original du code Java, mais divisée en plusieurs états avec des affectations de variables locales à faire de la logique plus facile à comprendre.

On peut aussi simplifier l'expression régulière, à l'aide de fini la répétition, comme suit:

boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+");

Encore une fois, donné un String de la longueur n, rempli avec le même char,

• .{0,1} vérifie si n = 0,1, PAS premier
• (.{2,})\1+ vérifie si n est un multiple de k >= 2, PAS premier

À l'exception de l'réticents modificateur ? sur \1 (omis pour plus de clarté), la regex est identique à l'original.

---

Plus de plaisir regex

La regex suivante utilise le même genre de technique; il doit être éducatif:

System.out.println(
    "OhMyGod=MyMyMyOhGodOhGodOhGod"
        .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!")
); // prints "Oh! My! God!"

Voir aussi

• Expressions régulières: qui est plus gourmand

Answer 3

Nice regex truc (bien que très inefficace)... :)

La regex définit non-primes comme suit:

N n'est pas premier si et seulement si N<=1 OU N est divisible par K>1.

Au lieu de passer de la simple représentation numérique de N pour le moteur d'expressions régulières, il est nourri avec une séquence de longueur N, composé d'une répétition de caractère. La première partie de la disjonction des contrôles pour N=0 ou N=1, et le deuxième à la recherche d'un diviseur K>1, à l'aide des références arrières. Il force le moteur d'expressions régulières pour trouver certains non vide de sous-séquence peut être répétée au moins deux fois afin de former la séquence. Si une telle sous-suite existe, cela signifie que sa longueur divise N, donc N n'est pas premier.

Answer 4

Il y a une explication dans cette page: http://paddy3118.blogspot.com/2009/08/story-of-regexp-and-primes.html (liée à cette page de code Rosetta), et une plus détaillée en http: //www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/ .

Answer 5

 /^1?$|^(11+?)\1+$/
 

Appliquer aux nombres après conversion en base 1 (1 = 1, 2 = 11, 3 = 111, ...). Les non-premiers correspondront à cela. Si cela ne correspond pas, c'est premier.

Explication ici .