Une regex pour savoir si un nombre est premier - lkdjiin's blog
Wow, je comprenais la regex, mais pas la subtilité mathématique derrière, mais là c'est bon.
On commence par transformer un nombre en une chaîne d'autant de "1" (5 deviendra 11111).
Le truc c'est le (11+?) au début qu'on met dans une variable (\1) et qu'on va rechercher. Il y a match si la chaîne contient un nombre entier de fois (11+).
Ca se passe en boucle : imaginons pour 9 : on cherche dans 111111111.
- On trouve "11", mais le (\1+) ne matche pas : il reste un "1" à la fin.
- Il reboucle alors et cherche "111", qu'il va chercher : ici "111" se trouve bien un nombre entier de fois dans la chaîne : il matche !
(normal, car 9%3 ==0)
S'il n'avait pas matché, alors il aurait recherché un nombre entier de 1111 puis de 11111.
Normalement, pour tester un nombre N, on regarde s'il est divisible par tous les nombres de 2 à N-1.
Ici, c'est la même chose, sauf avec une chaîne de caractères et un modulo sur le nombre de caractères (3»111, 4»1111, 5»11111, etc.).
Le dernier truc, c'est le « !~ » qui va retourner le contraire du matchage : retourne true si pas matche (nombre premier) et false si matche (nombre pas premier).
Jolie astuce, même si mathématiquement il n'y a rien de nouveau.
Et je doute que ce soit rentable niveau performances : tester 9 revient à tester 111111111, ça va. Tester 1234 revient à tester une chaîne longue de 1234 caractères, ça va. Mais pour tester 5 milliard, la chaîne pèse deja 5 Go en mémoire : impensable, n'importe quel opération modulo serait plus rapide.
(via seb)
On commence par transformer un nombre en une chaîne d'autant de "1" (5 deviendra 11111).
Le truc c'est le (11+?) au début qu'on met dans une variable (\1) et qu'on va rechercher. Il y a match si la chaîne contient un nombre entier de fois (11+).
Ca se passe en boucle : imaginons pour 9 : on cherche dans 111111111.
- On trouve "11", mais le (\1+) ne matche pas : il reste un "1" à la fin.
- Il reboucle alors et cherche "111", qu'il va chercher : ici "111" se trouve bien un nombre entier de fois dans la chaîne : il matche !
(normal, car 9%3 ==0)
S'il n'avait pas matché, alors il aurait recherché un nombre entier de 1111 puis de 11111.
Normalement, pour tester un nombre N, on regarde s'il est divisible par tous les nombres de 2 à N-1.
Ici, c'est la même chose, sauf avec une chaîne de caractères et un modulo sur le nombre de caractères (3»111, 4»1111, 5»11111, etc.).
Le dernier truc, c'est le « !~ » qui va retourner le contraire du matchage : retourne true si pas matche (nombre premier) et false si matche (nombre pas premier).
Jolie astuce, même si mathématiquement il n'y a rien de nouveau.
Et je doute que ce soit rentable niveau performances : tester 9 revient à tester 111111111, ça va. Tester 1234 revient à tester une chaîne longue de 1234 caractères, ça va. Mais pour tester 5 milliard, la chaîne pèse deja 5 Go en mémoire : impensable, n'importe quel opération modulo serait plus rapide.
(via seb)