Nombres premiers

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Arth

Bonjour,

Voici un de mes premiers messages sur ce forum.

J'aime beaucoup les nombres premiers, je trouves que ces nombres sont facinants. ( chacun fait ce qu'il peut )

Pour calculé des nombres premiers j'utilise cette algorithme:

je prend un nombre, je le divise par tout les nombres, un a un de ma liste, jusqua la racine du nombre tester. Si aucun resultat des divisions ne sont premier alors le nombre tester et un nombre premier et je passe au suivant.

J'ai programmer cela en C.

au debut je crée un fichier qui contient uniquement un nombre premier : 2, qui servira de premier test pour tout les autre

Citation:

#include <stdio.h>
int main ( void)
{
int deux = 2;
FILE * fichier;
fichier = fopen ("c:/fichier.txt","w");
if (!fichier)
{
printf("pb!");
return 1;
}
fprintf(fichier,"%d\n",deux);
fclose (fichier);
return 0;
}


apres je lance le programme enoncé plus haut.

Citation:

#include <stdio.h>
#include <math.h>
int main (void)
{
int fin_test = 10000000000;
int i;
int reste;
int nb;
int fin;
int racine;
FILE * fichier;
fichier = fopen("c:/fichier.txt","a+");
if (!fichier)
{
printf("pb!\n");
return 1;
}
fseek(fichier,0,SEEK_END);
fin = ftell(fichier);
for (i=3;i<=fin_test;i++)
{
rewind(fichier);
while(1)
{
fscanf(fichier,"%d\n",&nb);
reste = i % nb;
if( reste == 0 )
{
break ;
}
if(((ftell(fichier))==fin)||(nb>((sqrt(i))+1)))
{
fseek(fichier,0,SEEK_END);
fin = ftell(fichier);
printf("%d\n",i);
fprintf(fichier,"%d\n",i);
break ;
}
}
}
fclose(fichier);
return 0;
}


ce programme n'a rien de parfait... je travail a sont optimisation actuelement.
( c'est juste si ca interesse quelqu'un )

entre temps j'ai découvert un livre au CDI de mon établissement : Merveilleux nombres premiers de Jean-Paul Delahaye.
( c'est mon livre de chevet depuis :D )

il y a un passage que je n'arrive pas a saisir :

Citation:
Une méthode pour stocker des nombres premiers consiste à écrire les nombres sous la forme 30k + i, avec i compris entre 0 et 29. Dans une telle écriture, seuls les nombres pour lesquels i vaut 1, 7, 11, 13, 17, 19, 23 ou 29 peuvent être premiers: en effet, pour toutes les autres valeurs de i,on peut factoriser l'expression 30k + i, par exemple 30k + 5 = 5 ( 6k + 1 ). Avec un octet de mémoire ( unité de huit <<bits>> valant 0 ou 1 ), au lieu de coder un seul nombre premier, on code pour ces huit valeurs de i, par un 1 ou un 0, la nature première ou non de huit nombres dans une tranche de 30: on obtient donc une compression d'un facteur 30. En utilisant 210 à la place de 30, on code une tranche de longueur 210 avec 6 octets ( facteur de compression 35).



Je nage ...... merci de m'aider a comprendre.

Ou si quelqu'un a une autre idée pour fair une liste de nombres premiers.

Merci d'avance pour vos réponses.


Posted by: Arth

Je m'interesse aussi a la cryptologie, pour certain algorithme de cryptage comme RSA, il y as besoin de Grands nombres premiers.

Mais avec ma methode je n'arriverais pas a avoir de grand nombres premiers, je n'en suis qu'à des nombres composés de 9 chiffres.

Donc, quels est l'utilité d'une telle suite de nombre ?


Posted by: yos

C'est un début de méthode de crible : en ne prenant que les entiers congrus à 1, 7, 11, 13, 17, 19, 23, ou 29 modulo 30, on écarte d'emblée les multiples de 2, 3, 5. Avec 210, sont également écartés les multiples de 7.

Les nombres premiers de la tranche [90, 120] sont codés par 01111110 (code qui signifie que 90+1 n'est pas premier, 90+7 l'est, ...)


Posted by: Arth

Merci de ta reponse Yos.

Je n'ai pas tres bien compris le coup des modulo, je ne suis qu'en terminale sti electronique.

mais:

pour k = 0
30 k + 1 = 1
30 k + 7 = 7

tous les deux sont premiers, mais dans ma listes je n'aurais pas le 2, 3 et 5.

pour k = 1
30k + 19 = 49
7 * 7 = 49
49 n'est donc pas premier

pour k = 2
30k + 17 = 77
77 n'est pas premier

pour k = 3
30k + 1 = 91
91 n'est pas premier

Citation:
Les nombres premiers de la tranche [90, 120] sont codés par 01111110 (code qui signifie que 90+1 n'est pas premier, 90+7 l'est, ...)



Je ne voi vraiment pas le rapport excuse moi.


Posted by: Patastronch

pourtant yos a ete tres clair.

Par exemple dans ton code tu tests tous les nombres, mais as tu besoin de tester les nombres pairs ? les multiple de 3 ? de 5 ? voila pourquoi on te conseil d'utiliser 30k+i (mais ca peut etre une autre formule si tu veux en élaguer encore plus) avec i appartenant à {1, 7, 11, 13, 17, 19, 23, 29}

reprends l'exemple de Yos :

Les nombres premiers de la tranche [90, 120] (soit k=3) sont codés par 01111110

le premier zéro corespond a ton premier i, soit 90+1=91 n'est pas premier (car =0)
le second chiffre est un un qui correspond a ton second i , soit 90+7=97 qui est premier (car=1)
...

au lieu de parcourir de un en un, tu parcours avec :

Code:
for k in Les Entiers
  for i in {1, 7, 11, 13, 17, 19, 23, 29}
    si (30k+i) est premier ecrire le couple (k,i)
  end
end


Bien entendu tu commences à parcourir à 31, donc assure toi bien d'avoir déjà les nombre prémier inférieur a 30 dans ta liste ( correspondants aux couples (0,1) (0,2) (0,3) (0,5) ...(0,i)... (0,29)) , par contre inutile de tester si tes nombres sont divisible par 2, 3 ou 5 quand tu veut déterminer leur primalité, puisqu'on est deja sur qu'ils ne le sont pas (c'est le but du truc).

au final tu auras une suite enorme de couple (k,i) différents qui correspondront a 30k+i. ce qui te fera gagner enormément de place pour les grands nombres.
La méhode de stockag proposé par Yos (suite de 0 et de 1) ne me parait pas performante en niveau gain car dans les grands nombres tu auras beaucoup de 0 stockés qui définissent des nombres non premier et ca on s'en fout.


Par contre sache que l'écriture dans un fichier est une opération tres longue, et ca ne sert a rien de lire puis d'ecrire, puis de relire, puis d'écrire tout le temps et ca gache de beaucoup les performances de ton algo. Les ordinateurs ont de la ram, serts toi en c'est fait pour ca (pour éviter les accés au disque dur inutile).

Bon courage.










-