Home

Logithèque

TI82

Trouve les diviseurs d'un entier positif

Code

Ce programme nommé DIV2 appelle un sous-programme nommé tDIV2 (t=théta) qui doit être présent.

Ans->N

{0}->L5:1->C:1->K

2->L6(1)

If 2<dim(L6)

If (3/=L6(2)) or (5/=L6(3))

{2,3,5}->L6

prgmtDIV2

If 1=N:Goto 1

D->E:7+30*iPart((D-7)/30)->D

Repeat E^2>=N

1->J

Lbl 3:L6(J)->A

If 0=fPart(D/A):Goto 4

1+J->J

If J<=B:Goto 3

D->L6(J):J->B:D->E

Lbl 4:D+2->D

End

prgmtDIV2

Lbl 1:L5

Les signes "/=" en ligne 4 représentent la comparaison "est différent de", et "^2" en ligne 10 l'élévation au carré.

Le sous-programme tDIV2 (t=théta, nom impératif) est le suivant :

dim(L6)->B

Repeat D^2>=N

If K>B:Return

L6(K)->D

While 0=fPart(N/D)

N/D->N:D->L5(C)

1+C->C:End

1+K->K:End

N->L5(C):1->N

Les signes "/=" représentent la comparaison "est différent de", et "^2" l'élévation au carré.

Mode d'emploi

Saisir le nombre afin qu'il se trouve dans Ans. Exécuter le programme. La liste des diviseurs du nombre est affichée après un certain temps, les facteurs pouvant être répétés.

Exemple : 325461:prgmDIV2

renvoie : {3 157 691}

Mathématiques à l'oeuvre

C'est toujours la technique des divisions successives, mais dans ce cas précis on utilise un petit raffinement : on calcule d'abord la liste des nombres premiers inférieurs à la racine carrée du nombre courant. Comme cette liste est conservée entre les appels, on peut éventuellement gagner du temps si on cherche les facteurs d'un grand nombre d'entiers.

En fait la première chose que l'on fait est de tester les nombres premiers déjà présents dans la liste.

Fonctionnement du programme

Voici l'utilisation des variables :

A	Diviseur à tester
B	Dimension de L6
C	Pointeur sur L5
D	Nombre premier à ajouter à L6
E	Temporaire pour D
J	Pointeur sur L6
K	Pointeur sur L6
N	Nombre à diviser

On utilise la liste L6 pour conserver les nombres premiers entre appels successifs du programme. Le sous-programme tDIV2 réalise le test complet sur la liste existante, et le programme principal rallonge celle-ci si nécessaire.

Noter au début du programme principal un test vérifiant si la liste L6 contient bien la liste des nombres premiers (elle pourrait être écrasée ou effacée). La syntaxe 2->L6(1) est permise même sur une liste vide.

L5 contient la liste des diviseurs.

Ce programme est décevant, car de fait on factorise rarement beaucoup de nombres à la suite. La liste L6 est donc souvent effacée entre les appels, et sa génération est longue. Une astuce pourrait être implémentée dans le programme, celle de tester si les nombres premiers générés pour allonger L6 divisent le nombre N cible, au fur et à mesure de leur génération, afin de stopper l'allongement le plus tôt possible.

Par ailleurs, le stockage des sqrt(N/ln(N)) nombres nécessaires à décomposer tous les nombres premiers inférieurs ou égaux à N et la limite de 999 éléments dans les listes de la TI83 font que l'on ne peut factoriser les nombres supérieurs à 16 500 000 environ...