samedi 23 août 2014

Test de primalité d'un nombre entier.

Nous allons rechercher si un nombre impair supérieur ou égal à 3 est un nombre premier en utilisant l'algorithme de test élémentaire suivant:

K = 3
Début Test
{
    Si ( K > RacineCarrée(P) ) Alors ( P est Premier - Fin du Test )
    Si ( K divise P ) Alors ( P est non Premier - Fin du Test ) 
    K = K + 2
}
Retourne Début Test

Le programme suivant active le drapeau 1 (Flag 1) si le nombre testé est premier.

PGRM TOP
R001 LBL R
# Efface et désactive le drapeau 1 (Flag 1).
R002 CF 1
R003 STO P
R004 3
R005 STO K
R006 RCL P
# Racine carré de X.
R007 √(X)
R008 RCL K
R009 X > Y ?
R010 GTO R020
R011 RCL P
R012 X<>Y
R013 ÷
# FP signifie Fractional Part de P/K (Menu INTG choix 5).
R014 FP
R015 X = 0 ?
R016 GTO R023
R017 2
R018 STO + K
R019 GTO R006
# Active le drapeau 1 (Flag 1).
R020 SF 1
# CLSTK signifie vider les 4 niveaux du stack (Menu CLEAR choix 5).
R021 CLSTK
R022 RTN
R023 CLSTK
R024 RTN

Entrez votre nombre impair dans la ligne basse de l'écran de la calculatrice (registre X) et lancez le programme en faisant XEQ R ENTER.
Le drapeau 1 est activé si le nombre est premier, le chiffre 1 apparait alors sur la ligne d'indicateurs de la calculatrice.

Par exemple entrez 137 puis XEQ R ENTER. Le drapeau 1 s'active.
Voici quelques autres nombres à tester: 567 est non premier, 571 est premier, 2603 est non premier et 524287 est premier.
Vous pouvez faire chauffer le processeur en testant 2147483647 ;).

NB: Il ne sert à rien de tester les nombres pairs qui sont tous divisibles par deux et donc non premiers (Le seul nombre premier pair est 2).

Liens intéressants:
Les divers tests de primalité.
Test de primalité élémentaire.

A très bientôt :)

Aucun commentaire:

Enregistrer un commentaire