Math, nombres premiers : théorème de Wilson

[Ollivier]

Je copie ce court code ici aussi. Cet algo m'obsède. Il est d'une simplificité apparente à s'arracher les cheveux. Sa complexité réside dans la valeur du nombre dont l'échelle explose avec une précision telle qu'il stocke tous les nombres premiers que la factorielle va "couvrir".

Code : Tout sélectionner

Dim s.s(1)
s(0) = " = 0 donc c'est un premier"
fact + 1
Debug Chr($8000)
For n = 2 To 21
   Debug Rset(Str(fact), 24, " ") + "+1  % " + Str(n) + s(Bool((fact + 1) % n) )
   fact * n
Next

[Ar-S]

J'avoue être bien loin de m'intéresser aux nombres 1ers mais ton code est rigolo.
Pourquoi afficher le Chr($8000) ?

[Ollivier]

Ça aligne les colonnes.

[Mindphazer]

A part afficher un caractère chinois (ou japonais, je ne suis pas expert), ça ne fait rien d'autre chez moi...

耀
2+1 % 2 = 0 donc c'est un premier
3+1 % 3 = 0 donc c'est un premier
7+1 % 4
25+1 % 5 = 0 donc c'est un premier
121+1 % 6
721+1 % 7 = 0 donc c'est un premier
5041+1 % 8
40321+1 % 9
362881+1 % 10
3628801+1 % 11 = 0 donc c'est un premier
39916801+1 % 12
479001601+1 % 13 = 0 donc c'est un premier
6227020801+1 % 14
87178291201+1 % 15
1307674368001+1 % 16
20922789888001+1 % 17 = 0 donc c'est un premier
355687428096001+1 % 18
6402373705728001+1 % 19 = 0 donc c'est un premier
121645100408832001+1 % 20
2432902008176640001+1 % 21

[Ollivier]

A part afficher un caractère chinois (ou japonais, je ne suis pas expert), ça ne fait rien d'autre chez moi...

C'est normal : tu n'es pas sur un ordi en carton avec "Chewing-Dose 10" dessus.

A part afficher un caractère chinois (ou japonais, je ne suis pas expert),[...]

J'ai déjà vu une chinoise et une japonaise s'engueuler : il vaut mieux dicerner, c'est très différent, je te l'assure, tellement opposé qu'à part sourire jaune, je ne pouvais plus rien faire...

[Mindphazer]

C'est normal : tu n'es pas sur un ordi en carton avec "Chewing-Dose 10" dessus

Sisi
J'ai testé sur un ordi au boulot, c'est bel et bien un Win10
Cela dit, j'ai également testé sur mon Mac. Résultats identiques.
J'ai toujours ce caractère, disons, extreme-oriental (je n'oserai pas dire à un chinois qu'il ressemble à japonais, et inversement...)

[Ollivier]

Code : Tout sélectionner

Debug "Bonjour"
Debug Chr($8000)
Debug "Bonjour"

Le caractère chinois active une police type "Courier" pour permettre de respecter les colonnes (les caractères ont la même largeur).

J'avoue être bien loin de m'intéresser aux nombres 1ers mais ton code est rigolo.

Ah, c'est sûr, il y a un mur. Tout est parfait jusqu'à 21. Après, c'est dead. Tu peux essayer avec des grands nombres (chaînes ou en binaire dur) : tu vas déceler quelques nombres premiers supplémentaires, et puis tu te reprends un mur (mémoire saturée).

Le nombre en maths se traduit par une récursivité en logique. Ils sont infinis en maths, mais finis en logique.

La fonction factorielle est tellement redondante que tu peux lui modifier des chiffres au hasard dedans, et la "réparer" (en théorie).

[Ollivier]

A part afficher un caractère chinois (ou japonais, je ne suis pas expert), ça ne fait rien d'autre chez moi...

耀
2+1 % 2 = 0 donc c'est un premier
3+1 % 3 = 0 donc c'est un premier
7+1 % 4

Et tu pouvais pas le dire plus tôt que je m'étais piné ?

Il y a un "+ 1" dans (fact + 1) que j'ai laissé en trop... C'est 1+1 %2 qui donne zéro, etc...

[SPH]

Pour en revenir au thème, va t'en prouver que 127 est un nombre premier !!
Le chiffre à moduler est trop "immaniable"...

[Mindphazer]

Code : Tout sélectionner

Debug "Bonjour"
Debug Chr($8000)
Debug "Bonjour"

Le caractère chinois active une police type "Courier" pour permettre de respecter les colonnes (les caractères ont la même largeur).

Heuuuuuuu... Pas chez moi. Le premier bonjour et le second ont absolument la même police, qui n'est pas Courier :
Bonjour
耀
Bonjour

[Mindphazer]

Et tu pouvais pas le dire plus tôt que je m'étais piné ?
Il y a un "+ 1" dans (fact + 1) que j'ai laissé en trop... C'est 1+1 %2 qui donne zéro, etc...

J'ai préféré te laisser te corriger

[Ollivier]

Et tu pouvais pas le dire plus tôt que je m'étais piné ?
Il y a un "+ 1" dans (fact + 1) que j'ai laissé en trop... C'est 1+1 %2 qui donne zéro, etc...

J'ai préféré te laisser te corriger

Affichage corrigé

[Ollivier]

Pour en revenir au thème, va t'en prouver que 127 est un nombre premier !!
Le chiffre à moduler est trop "immaniable"...

C'est un mur : incalculable, par manque de temps à la main. Par informatique, c'est plus rapide, mais si on veut vérifier la primalité de tous les nombres, ça reste trop long aussi.

Je crois qu'il y a une astuce de calcul, mais là encore, ça reste plus gourmand en ressource CPU que le crible d'Eratosthène.

Code : Tout sélectionner

Procedure isPrime(p)
 Protected a = p - 1
 Protected i
 For i = (p - 2) to 2 step -1
  a * i
  a % p
 next
 a + 1
 ProcedureReturn Bool(a = p)
EndProcedure

[SPH]

Reste que l'équation est belle quand même.

[Ollivier]

Fais-moi une petite chrono sympa. Donne-moi des durées obtenues, que je vois ma défaite :

Code : Tout sélectionner

OpenConsole()
For i = 1 to 10
 n = pow(10, i) - 7
 t0 = elapsedMilliseconds()
 isPrime(n)
 t1 = elapsedMilliseconds()
 PrintN(str(i) + " chiffre(s) : " + chr(9) + str(t1 - t0) + " ms")
Next
Input()

Ça donne quoi ?