Méthode Ruby isPrime
('1' * N) !~ /^1?$|^(11+?)+$/
sur le net, j'ai trouvé ce morceau de code Ruby qui fonctionne pour N >= 0 qui détermine si oui ou non N est un prime. De ce que je peux dire, ça ressemble à jouer avec regex mais je n'ai aucune idée de comment ça marche. Quelqu'un pourrait-il me dire comment il fonctionne?
7 réponses
vous pouvez trouver une longue explication de ce code ici: http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
c'est probablement hors sujet, mais dans Ruby 1.9, vous pouvez faire ceci:
require 'mathn'
38749711234868463.prime?
=> false
require 'prime'
Prime.prime?(4)
# => false
Prime.prime?(5)
# => true
ou:
require 'prime'
Prime.instance.prime?(4)
# => false
Prime.instance.prime?(5)
# => true
Voir aussi Quel est le regex le plus brillant que vous ayez utilisé? (et oui, je peux confirmer que ce regexp a été écrit à l'origine par Abigail. Je l'ai même entendu expliquer comment cela fonctionne:)
plus grand diviseur commun (gcd):
/^(1+)*=+$/.match('1' * x + '=' + '1' * y)[1].length
ceci et is_prime fonctionnent à peu près de la même manière. Il essaie toutes les combinaisons avant d'abandonner.
celui-ci essaiera de diviser le premier nombre en parties égales, et de faire correspondre le deuxième nombre avec une ou plusieurs de ces parties. S'il trouve une correspondance, il retourne la longueur de la partie sélectionnée.
encore un autre blog avec une assez bonne explication: célèbre Perl One-Liners Explained (part III)
si la longueur d'une chaîne de 1's est composite, alors la chaîne peut être décomposée en plusieurs substrats identiques, comme 111111 - > 11 11 11
par exemple, 1111111111, a 10 1's, et il correspond à (11){5} ou (11111){2}, où {2} signifie répété 2 fois. 111111111, has 91, and it matches (111) {3}.
en généralisant le compte de 1's et le nombre dans {}, le regexp est
/(1{2,}){2,}/ .
Cependant, 1{2,} peut aussi être écrit comme 11+, et (...){2,} peut être réécrit en (...)\1+, avec des références arrières.
la partie ^1?$ dans les premiers contrôles d'alternance pour les cas 0 et 1.