Primaly

Un article de Mwyann.info.

   Démarrer

      

Ceci est un programme fonctionnant sous Windows. En principe, mes programmes pour Windows sont développés avec Delphi, ils devraient donc fonctionner avec n'importe quel Windows 32 bits, commençant donc par Windows 95. Cependant, certains programmes peuvent nécessiter l'utilisation de librairies ou de fonctions disponibles uniquement dans des versions ultérieures de Windows. Certains programmes peuvent également fonctionner sous Linux grâce à Wine, mais rien n'est moins sûr. Lisez la description du programme pour en savoir plus, ou contactez-moi.

   

 

A propos du projet
SystèmeWindows
Compatible2000/XP/2003
Étape de dév.Fonctionnel
LangageDelphi
Création02/2004

 


Sommaire

Méthode pour déterminer la primalité

(D'après moi-même. Tiré d'un document que j'avais écrit à ce sujet.)

Un beau jour, dans un devoir de spécialité maths, un exercice nous propose de résoudre le problème suivant :

« Soit k un entier naturel > 0, et P un nombre premier. Vérifier que P s’écrit de la forme : P=6k-1 ou P=6k+1 »

Ce problème vient de Fermat. Je n’ai malheureusement pas pu faire cet exercice, car il y en avait d’autres plus longs à faire. Mais cela m’a mis la puce à l’oreille, et étant déjà intéressé par la recherche des nombres premiers, j’ai essayé de creuser une piste à partir de ces formules.

Commençons par construire une liste de nombres en fonction de k :

k
6k-1
6k+1
1
5
7
2
11
13
3
17
19
4
23
25
5
29
31
6
35
37
7
41
43
8
47
49
9
53
55
10
59
61
11
65
67
12
71
73
13
77
79
14
83
85
15
89
91
16
95
97

On remarque que tous les nombres premiers sont présents, plus quelques intrus (en gris dans le tableau). Le but est donc d’éliminer ces intrus. A première vue, il ne semble pas facile de déterminer lesquels sont bons, lequels sont mauvais. Ayant généré une liste plus longue de ces nombres, j’ai d’abord essayé de trouver la fréquence des nombres multiples de 5, de 7, de 11… en calculant l’écart entre deux nombres multiples. Et voici les résultats :

Multiple de :
5
7
3
7
3
7
3
7
3
7
9
5
9
5
9
5
9
5
11
15
7
15
7
15
7
15
7
13
17
9
17
9
17
9
17
9
17
23
11
23
11
23
11
23
11
19
25
13
25
13
25
13
25
13

On remarque que les nombres apparaissent à une fréquence qui elle-même revient fréquemment ! Nous pouvons alors construire un nouveau tableau :

Multiple de :
5
7
11
13
17
19
23
25

Fréquence 1 :

7
9
15
17
23
25
31
33

Fréquence 2 :

3
5
7
9
11
13
15
17

D’après ce tableau, il n’est pas difficile de trouver une relation entre les fréquences : il s’agit simplement pour la 1ère fréquence d’ajouter 2 puis 6 puis 2 puis 6… et pour la 2ème fréquence c’est une banale suite arithmétique de raison 2.

Dans mon tableau, je n’ai pas utilisé les nombres premiers mais la formule de départ (25 apparaît mais n’est pas premier), pour faciliter les calculs. Car nous pouvons associer chaque nombre de la formule à un autre nombre :

Index : 1 2 3 4 5 6 7 8
Liste : 5 7 11 13 17 19 23 25

Appellons i l’index de chaque nombre. Le calcul des fréquences est donc :

Fréquence 1 = 3+4*i-2*((i+1) mod 2)
Fréquence 2 = 3+2*(i-1)

A partir de là, mon algorithme se base sur le calcul inverse de la formule de départ : soit P le nombre à tester, effectuons les opérations inverses :

P1 = (P+1)/6
P2 = (P-1)/6

P1 et P2 correspondent à k dans la formule de départ. Or k est entier. Donc si P1 ou P2 est entier, alors P a une chance d’être premier. Sinon, P est divisible par 2 et/ou 3. Appellons C la « constante », correspondant à l’un des deux nombres entiers P1 ou P2. Pour que chaque nombre premier P ait son numéro unique C associé et vice versa, prenons : C=P1*2-1 ou C=P2*2. Mais tous les C ne sont pas forcéments associés à un nombre P premier. Il y a des intrus dans la liste. Au lieu de calculer à partir de P, préférons travailler avec C, qui est plus petit et plus simple. C’est avec lui que nous allons déterminer si P est premier ou non. Nous pouvons, grâce aux formules précédentes, trouver quels nombres ne sont pas premiers, par rapport à leur index. Il suffit d’ajouter les fréquences, comme on l’a vu plus haut. A la page suivante, vous trouverez l’extrait du tableau contenant les index des nombres non premiers. Le but est donc de trouver C dans ce tableau. Si C est présent, cela veut dire que C fait partie des nombres donc la valeur signifie que P est non premier… En clair, si il y a C, alors P n’est pas premier. Le principal problème est donc de trouver une méthode efficace pour trouver une grande valeur dans un tableau gigantesque. Nous pouvons néanmoins remarquer que le tableau est symétrique, donc nous n’avons que la moitié à étudier.

J’ai réalisé un programme informatique qui propose de trouver la primalité d’un nombre quelconque inférieur à 2^63-1 (9223372036854775807) avec une vitesse très correcte. Cependant, je me sers des fonctions du processeur pour les calculs, et ses capacités étant limitées, les nombres supérieurs à 6442450944 font ralentir le calcul. Malgré tout, les nombres premiers immédiatement inférieurs et supérieurs à ce nombre sont respectivement 6442450939 et 6442450967, et sont résolus en 60 millisecondes sur un processeur Pentium 3 à 500MHz. D’autres résultats : 2646216567629137 : 7,5 sec ; 12646216567629137 : 17,8 sec ; 312646216567629137 : 2,27 min. Autres possibilités : Trouver les facteurs premiers, et effectuer des tests sur plusieurs nombres, en rafale.

Réalisé par : Yann Le Brech, élève de TS au lycée Pierre Guéguin. 2004 Le devoir a été donné le mardi 27 janvier 2004, ce document est fini le mercredi 4 février 2004.

Tableau des index non premiers

Ceci est un extrait de tableau qui permet de déterminer la primalité d'un nombre grâce à ma méthode. Regardez les exemples plus bas pour savoir comment s'en servir.


Image:Primaly_index.png

Exemples

P = 241

Prenons par exemple P=241. Effectuons les divisions :

(241+1)/6 = 40,333333
(241-1)/6 = 40

Prenons C = 40*2 = 80 car 40 est entier. Le nombre 80 n'apparaît pas dans le tableau. 241 est donc premier.

P = 213

Prenons un autre exemple : P=213. Les divisions donnent :

(213+1)/6 = 35,666666 
(213-1)/6 = 35,333333

Aucun des nombres n’est entier, P est divisible par 2 et/ou 3. Effectivement, il s’agit de 3*71.

P = 203

Un dernier exemple : P=203. Les divisions donnent :

(203+1)/6 = 34
(203-1)/6 = 33,66666666

Prenons C = 34*2-1 = 67. Or 67 apparaît dans le tableau dans la colonne 9 et ligne 2. P est donc composé. Nous pouvons même dire qu’il est divisible par les nombres correspondants à i=9 et i=2 (colonnes et lignes), soit 29 et 7. Effectivement, 203 = 29*7.