Home
Logithèque
|
Home |
|
Logithèque |
TI82
Test probabiliste de la primalité <<<<A REVOIR>>>>
Code
Ce programme nommé PRIME appelle un sous-programme nommé tMODPOW (t=théta) qui doit être présent.
Input N:0->D
If N>1:Disp N
Les signes "^2" dans DIV représentent la fonction "élévation au carré".
Le sous-programme tMODPOW (nom impératif) est le suivant :
1->M:Lbl A
Q/2->Q
If 0/=fPart Q
round(PfPart (MN/P),0)->M
round(PfPart (N^2/P),0)->N
iPart Q->Q
If 0/=Q:Goto A
Les signes "/=" représentent la comparaison "est différent de", et "^2" l'élévation au carré.
Mode d'emploi
Exécuter le programme. Saisir le nombre. Un message est affiché signalant "PREMIER" ou "COMPOSE" ou "??" selon que le nombre est premier, non premier ou de nature indéterminée.
Mathématiques à l'oeuvre
Le petit théorème de Fermat signale que si P est premier alors pour tout nombre A, (A^(P-1)-1) est divisible par P.
On fait des divisions successives, d'abord par 2, 3 , 5 et 7, puis en balayant les entiers qui ne sont pas diviseurs de 2, 3 ou 5. Pour cela on utilise un cycle d'incréments du diviseur de {4,2,4,2,4,6,2,6} en partant de 7.
Avec cette technique, un arbitrage doit être fait entre le nombre de nombres premiers dont on ne veut pas revoir les multiples, et la longueur du cycle dans le programme. Mon avis est que le cycle avec {2, 3, 5} qui est long de 8 éléments, est un bon compromis pour une machine de poche.
Au fait, la longueur du cycle est-elle toujours 2 à la puissance le nombre de diviseurs ?
Fichiers
Voici les deux programmes pour chargement direct dans votre machine via le "GraphLink".