Nombre Premier

GW-Basic, utilisé par PC-Basic

Programme avec Texte Seulement

PC-BASIC

Bien que l'ancien mathématicien Euclide n'ait probablement pas été le premier à prouver l'infinité des nombres premiers - c'est-à-dire qu'il existe une quantité incalculable de nombres premiers - sa preuve est sûrement la plus célèbre, nécessitant peu de connaissances mathématiques préalables.

Rappelons qu'un nombre premier est tout nombre entier avec seulement lui-même et le nombre un comme diviseurs (bien que le nombre un, par définition, ne soit pas premier).* Euclide a commencé par supposer que le nombre de nombres premiers était fini, et nous avions une liste de tous. Il a ensuite dit de multiplier tous ces nombres premiers ensemble et d'appeler ce produit P.

Maintenant, ajoutez un à P ; désigner ce nouveau nombre Q. Il y a deux possibilités : soit Q est premier (c'est-à-dire que le nombre de nombres premiers n'est finalement pas fini), soit il ne l'est pas. Mais si Q n'est pas premier, alors il y a un nombre premier qui se divise en Q, mais ce ne peut pas être un nombre de l'original.

Le nombre un n'est pas premier car, lors de la création d'un arbre factoriel de n'importe quel nombre entier, le nombre un peut être amené à se répéter autant de fois que vous le souhaitez, contrairement à tout autre facteur premier. Étant donné que chaque décomposition de nombre entier doit avoir un nombre unique de facteurs premiers (pensez aux nombres premiers comme les «atomes» qui construisent des nombres entiers - leur apparence ou leur absence n'est pas simplement arbitraire), le nombre un ne peut pas être considéré comme premier.

Donc, dans tous les cas, nous avons une contradiction : chaque nombre premier ne peut pas figurer sur la liste originale "finie" des nombres premiers d'Euclide. Ainsi, il doit y avoir une infinité de nombres premiers.

Nous ne pouvons jamais lister tous les nombres premiers, et aucun ordinateur ne peut tous les afficher à l'écran, peu importe le temps que nous attendons. Mais il existe des algorithmes pour déterminer si un nombre est premier, ainsi que pour générer rapidement de nombreux nombres premiers.

L'un des plus anciens de ces derniers algorithmes s'appelle le crible d'Eratosthène et fonctionne de manière itérative. À partir des plus petits nombres premiers, les multiples de chaque nombre premier sont déclarés composites, laissant les nombres premiers dans leur sillage. D'autres algorithmes testent les nombres premiers dans un ordre séquentiel.

PRIMES.BAS vous invite à vérifier si un seul nombre est premier ou simplement à voir les nombres premiers séquentiels rapides. Pour voir si un seul nombre est premier, tapez-le : l'ordinateur vérifiera rapidement si le nombre a des diviseurs en plus de un, rapportera les résultats et demandera un autre nombre. Si un nombre négatif est saisi, le programme vous renvoie au menu principal.

L'option nombres premiers séquentiels affiche les nombres premiers dans un ordre séquentiel aussi rapidement que possible à l'écran. La boucle peut être arrêtée à tout moment en appuyant sur la touche ESCAPE.

Lorsque vous vérifiez si un nombre est premier, notez que seuls les diviseurs (à l'exclusion du nombre un) jusqu'à la racine carrée du nombre donné doivent être vérifiés séquentiellement : voir les lignes 40 et 140. Sur ces deux lignes, la fonction INT, ou convert-to-integer, est utilisée ; si le quotient à l'intérieur de l'INT est un entier, le nombre P n'est pas premier, mais composé.

La liste des nombres premiers est testée séquentiellement. C'est inefficace - regardez la boucle pendant un moment, et vous remarquerez comment le programme ralentit progressivement à chaque niveau supérieur.

Peut-être que modifier le programme pour utiliser le crible d'Eratosthène, ou un autre algorithme (nombres premiers de Mersenne, n'importe qui ?), serait plus efficace.

1 REM PRIMES.BAS
5 KEY OFF:SCREEN 9:COLOR 15,1:CLS
6 GOTO 200
10 CLS
20 PRINT "EST-CE UN NOMBRE PREMIER ?"
22 INPUT "SAISIR UN NOMBRE A VOIR (ou négatif pour arrêter):";P
23 IF P=1 THEN PRINT "PAS PREMIER, PAR DÉFINITION":GOTO 20
24 IF P=0 THEN PRINT "PAS PREMIER":GOTO 20
25 IF P<0 THEN 5
30 FOR L=2 TO INT(SQR(P))
40 IF (P/L)=INT(P/L) THEN PRINT P;" n'est pas premier !! (";L;" est un diviseur)"'GOTO 20
50 NEXT L
60 PRINT P;" est un nombre premier"
70 PRINT:GOTO 20
100 CLS:P=1
120 P=P+1
125 IF INKEY$=CHR$(27) THEN 200
130 FOR L=2 TO INT(SQR(P))
140 IF (P/L)=INT(P/L) THEN GOTO 120
150 NEXT L
160 PRINT P;
170 GOTO 120
200 CLS
205 PRINT "Nombre Premier":PRINT
210 PRINT "Faites Votre Choix:"
220 PRINT:PRINT "1. Vérifier si un nombre est premier"
230 PRINT "2. Voir une liste de nombres premiers (Appuyez sur ESC pour arrêter)"
240 PRINT "3. EXIT"
250 INPUT PROMPT
260 IF PROMPT=1 THEN 10
270 IF PROMPT=2 THEN 100
280 IF PROMPT=3 THEN CLS:END
290 GOTO 250