G
RIP
NOMBRES
CASIO
DECOMPOSITION D’UN NOMBRE
EN FACTEURS PREMIERS
Problème
ES
TOUT ES
LATRIC
CALCU IO
CAS
Ce développement a déjà été publié dans la revue n°23. Nous le redonnons ici afin
d’homogénéiser le dossier et de produire le listing du programme pour les anciennes
calculatrices.
Principe
Un nombre A étant donné, on le divise par la suite des nombres
premiers, en retenant ceux qui sont diviseurs, autant de fois que
nécessaire, jusqu’à ce que le nombre premier soit supérieur à la
racine carrée du dernier quotient entier.
La réèlle difficulté d’une telle méthode est la génération de la suite
des nombres premiers.
Pour ce faire, nous remarquerons qu’en dehors de 2 et de 3, tout
nombre premier peut s’écrire sous l’une des formes:
6p + 1
ou
6p + 5.
Ce sont donc les nombres de cette forme que nous utiliserons
comme diviseurs.
Ce qui ne signifie pas que tous ces nombres seront premiers
(comme par exemple 25 = 6 x 4 + 1).
Cependant, nous détenons là un bon moyen de déterminer, sans
trop de difficultés, tous les nombres premiers (plus quelques uns
qui ne le seront pas). Nous effectuerons donc quelques divisions
inutiles qui ne porteront aucun préjudice ni à la rigueur de la
démarche ni à la rapidité d’obtention du résultat.
Génération des nombres 6p + 1 et 6p + 5.
Plutôt que de donner à p les valeurs 0, 1, 2, 3, etc… on remarquera,
qu’à partir de 5, on obtient les suivants en:
• ajoutant 2
5 + 2 = 7
• ajoutant 4
7 + 4 = 11
• ajoutant 2
11 + 2 = 13
• ajoutant 4
13 + 4 = 17
etc…
Utilisation
et d’une manière générale, si on a le nombre 6p+1
• on ajoute 4: 6p+1 + 4 = 6p+5
soit 6p+5
• on ajoute 2: 6p+5 + 2 = 6(p+1)+1
soit 6p+1
etc…
Un problème se pose alors: comment obtenir successivement 2
puis 4, en ne faisant qu’une seule série d’opérations ?
N étant le diviseur, on appelle M la mémoire qui doit contenir 2 ou
4.
M vaut 2; en ajoutant 2, M vaut 4
M vaut 4; en ajoutant -2, M vaut 2.
Il faut donc ajouter à M tantôt 2, tantôt -2.
Simulons cette situation:
N = 5 , M = 2 , J = -2:
áN)
• On augmente N de M (N+Má
soit N=7
áJ)
• On prend l’opposé de J (-Já
soit J=2
áM)
• On augmente M de J (M+Já
soit M=4
áN)
• On augmente N de M (N+Má
áJ)
• On prend l’opposé de J (-Já
áM)
• On augmente M de J (M+Já
soit N=11
soit J=-2
soit M=2
áN)
• On augmente N de M (N+Má
áJ)
• On prend l’opposé de J (-Já
áM)
• On augmente M de J (M+Já
etc…
soit N=13
soit J=2
soit M=4
On lance le programme principal FACT PRM.
Exemple: 147
Exemple: 456812
(on presse EXE après
chaque affichage de diviseur)
(on presse EXE après
chaque affichage de diviseur)
Exemple: 360
Exemple: 12347
(on presse EXE après
chaque affichage de diviseur)
(on presse EXE après
chaque affichage de diviseur)
CASIO
DECOMPOSITION D’UN NOMBRE
EN FACTEURS PREMIERS
ALGORITHME:
• Demander A.
•N=2
◊ Procédure Divisions de A par N
•N=3
◊ Procédure Divisions de A par N
• N = 5 et M = 2 et J = -2
Faire:
◊ Procédure Divisions de A par N
• Augmenter N de M
• J devient -J
• Augmenter M de J
Tant que N ≤ √A
• Si A≠1 alors écrire A et FIN
• Sinon FIN
A
N° du programme
Prog 5
◊ Procédure Divisions de A par N:
Tant que N divise A:
• Ecrire N
• Remplacer A par le quotient A/N
Fin de Tant que
FIN de procédure
N
Nom du programme
FACT PRM
'FACT 1ä
"NOMBRE"?ÊAä
2ÊNä
Prog 6ä
3ÊNä
Prog 6ä
5ÊN:2ÊM:-2ÊJä
Lbl 0ä
Prog 6ä
N+MÊNä
-JÊJä
M+JÊMä
N≤√A…Goto 0ä
A≠1…A¶
"FIN"
ClrText
ä
ClrTextä
"NOMBRE"?áA
ä
"NOMBRE"?áAä
2áN
ä
2áNä
Prog "DIVISE"
ä
"DIVISE"ä
3áN
ä
3áNä
Prog "DIVISE"
ä
"DIVISE"ä
5áN:2áM:ù2áJ
ä
5áN:2áM:ù2áJä
Do
ä
Doä
Prog "DIVISE"
ä
"DIVISE"ä
N+MáN
ä
N+MáNä
ùJáJ
ä
ùJáJä
M+JáM
ä
M+JáMä
LpWhile NÆ•A
ä
NÆ•Aä
If A¨1
ä
A¨1ä
Then Aª
IfEnd
ä
IfEndä
"FIN"
Nom du programme
Nom du programme
Prog 6
DIVISE
'DIVISEä
Lbl 2ä
A/NÊXä
Frac X≠0…Goto 9ä
N¶
XÊAä
Goto 2ä
Lbl 9
G
RIP
NOMBRES
While Frac (A§N)=0
ä
(A§N)=0ä
Nª
A§NáA
ä
A§NáAä
WhileEnd
N
G
DECOMPOSITION D’UN NOMBRE
RIP
NOMBRES
CASIO
EN FACTEURS PREMIERS (suite)
Type N
sauf
0G
fx-691 0
H2
GRAP
Problème
Le programme de la fiche précédente présente de nombreux avantages:
- Pas très long à enregistrer.
- Exécutable sur les fx-6910G et GRAPH 20.
- Très performant dans la rapidité d’exécution des calculs.
Mais, son seul vrai défaut, est de donner la liste détaillée des différents facteurs premiers, par exemple
3; 3; 3; 3 au lieu de 3^4.
Nous allons donc arranger cela, dans cette fiche.
Cependant, comme nous allons exploiter les possibilités de mise en page qu’offre l’instruction Locate,
ces programmes ne seront pas valides sur les fx-6910G et GRAPH 20.
Voir programmes au dos.
Utilisation
On lance le programme principal FACT 1P.
Autres exemples:
• On affiche le nombre: 610304
• On presse EXE.
Les points simulent le
partage de l’écran en
deux colonnes
• On lit: 610304 = 212 x 149
• FIN indique que la décomposition
est terminée.
Tant que le carré noir est affiché, la
calculatrice calcule.
Et, … 4 minutes plus tard …, elle
affiche le second facteur.
CASIO
DECOMPOSITION D’UN NOMBRE
EN FACTEURS PREMIERS (suite)
Indications
G
RIP
NOMBRES
• On nomme le premier programme:
• On nomme les sous-programmes (procédures):
FACT 1P.
- DIVISE1
- ECRAN
- PREMIER
- AFFICHE
Nom du programme
ECRAN
Nom du programme
FACT 1P
ClrText
ä
ClrTextä
"---DECOMPOSITION----"
ä
"---DECOMPOSITION----"ä
"EN FACTEURS PREMIERS"
ä
PREMIERS"ä
" "
ä
"ä
"NOMBRE"?áA
ä
"NOMBRE"?áAä
Prog "ECRAN"
ä
"ECRAN"ä
2áN:0á–
ä
2áN:0á–ä
Prog "DIVISE1"
ä
"DIVISE1"ä
3áN
ä
3áNä
Prog "DIVISE1"
ä
"DIVISE1"ä
5áN:2áM:ù2áJ
ä
5áN:2áM:ù2áJä
Do
ä
Doä
Prog "DIVISE1"
ä
"DIVISE1"ä
N+MáN
ä
N+MáNä
ùJáJ
ä
ùJáJä
M+JáM
ä
M+JáMä
LpWhile NÆ•A
ä
NÆ•Aä
If A¨1
ä
A¨1ä
Then If –=1
ä
–=1ä
Then AáX:1áP
ä
AáX:1áPä
Prog "AFFICHE"
ä
"AFFICHE"ä
Else Prog "PREMIER"
ä
"PREMIER"ä
ä
IfEnd
IfEndä
IfEnd
ä
IfEndä
Locate 19,1,"FIN"
ClrText
ä
ClrTextä
2áL:0áC
ä
2áL:0áCä
Locate 1,1,"A="
ä
1,1,"A="ä
Locate 3,1,A
ä
3,1,Aä
For 2áZ To 7
ä
7ä
ä
Locate 11,Z,"."
11,Z,"."ä
Next
Ce sous-programme prépare l’écran pour un affichage des facteurs premiers sur deux colonnes.
Nom du programme
PREMIER
Locate 1,2,"---------------------"
ä
1,2,"---------------------"ä
Locate 1,3,"
EST PREMIER
"
"ä
ä
Locate 1,4,"---------------------"
Ce sous-programme affiche que le nombre est premier (quand
c’est la cas).
AFFICHE
Nom du programme
DIVISE1
0áP
ä
0áPä
While Frac (A§N)=0
ä
(A§N)=0ä
NáX:P+1áP:1áW:1á–
ä
NáX:P+1áP:1áW:1á–ä
A§NáA
ä
A§NáAä
WhileEnd
ä
WhileEndä
If W=1
ä
W=1ä
Then Prog "AFFICHE"
ä
"AFFICHE"ä
IfEnd
If L>7
ä
L>7ä
Then 2áL:11áC
ä
2áL:11áCä
IfEnd
ä
IfEndä
Locate C+1,L,X
ä
C+1,L,Xä
Locate C+8,L,"^"
ä
C+8,L,"^"ä
Locate C+9,L,P
ä
C+9,L,Pä
1+LáL:0áW
Ce sous-programme affiche les uns sous les autres les facteurs
premiers sous la forme X^P. Quand les (7-1) lignes d’affichage de
la colonne de gauche sont prises, on passe à la colonne de droite
(L=2 ; C=11).
">
