Aujourd’hui, nous nous intéressons aux nombres premiers et à la façon de les trouver. Pour cela, voilà un algorithme assez simple qui permet de trouver un nombre n de nombre premier. Dans sa première version, l’algorithme recommençait à calculer à partir de 5 (si ma mémoire est bonne ;) ) à chaque exécution. Dans sa version actuelle, nous pouvons maintenant reprendre les calculs à partir du dernier nombre premier trouvé. Quelques améliorations pourront néanmoins être apporter comme la possibilité d’interrompre le programme alors qu’il teste des nombres et de le relancer sans avoir à repartir du dernier nombre premier, la gestion des grands nombres pourrait être à revoir. Nous pouvons également envisager la division du fichier contenant les nombres premiers en plusieurs autres fichiers tous les x nombres.
L’algorithme est présenté en code C et repose sur ce que mon professeur de sécurité désignait il y a quelques jours comme la « méthode naïve »; puisqu’il existe d’autres méthodes, permettant de s’assurer qu’un nombre n’est pas premier entre autres (mais pas d’équivalence ici, si le nombre n’est pas premier, le théorème ne permet pas de monter qu’il l’est) et dont je parlerais certainement dans un autre article.
Au jour d’aujourd’hui, notre fichier fait 969 376 620 octets et est trop grand pour être ouvert par certains éditeur de texte :D. Pour déterminer si un nombre est premier, l’algorithme va regarder le résultat de la division du nombre testé par les nombres premiers déjà présent dans le fichier. Si le reste vaut 0, le nombre testé est divisible par un autre nombre que 1 ou lui-même, il n’est donc pas premier. On peut arrêter ce test, lorsque le nombre premier utilisé dans la division euclidienne est supérieur à la racine carré du nombre testé et ainsi gagner du temps. De même, l’incrémentation des nombres testés de 2 en 2 à partir d’un entier impair permet de ne jamais tester les nombres pairs puisque nous les savons tous divisibles par 2. Le lien vers un dossier contenant le code et les fichiers qu’il utilise: Algorithme Nombres Premiers. Place maintenant au programme:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int premier(int test);
int main(void)
{
/*VARIABLE:
recherche: le nombre de nombre premier à rechercher
dernier: le dernier nombre testé
lors de l'appel précédent au programme,
contenu dans dernier.txt*/
int recherche, dernier;
FILE *fichier_dernier_nbr;
FILE *fichier;
recherche=100;
dernier=0;
/*Initialisation du dernier nombre testé
dernier est obligatoirement impair*/
fichier=NULL;
fichier_dernier_nbr = NULL;
fichier_dernier_nbr = fopen("dernier.txt", "r+");
if (fichier_dernier_nbr != NULL)
{
fscanf(fichier_dernier_nbr, "%d", &dernier);
fclose(fichier_dernier_nbr);
}
/*On recherche autant de nombre premier
que le contenu de recherche*/
while(recherche>0)
{
if(premier(dernier))
{
/*Le nombre testé est premier*/
/*printf("%d:Premier\n", dernier);*/
/*On enregistre le nombre à la fin du fichier*/
fichier = fopen("test.txt", "r+");
fseek(fichier, 0, SEEK_END);
fprintf(fichier, "%d\n", dernier);
fclose(fichier);
/*On décrémente le nombre de nombre premier
encore à trouver*/
recherche--;
}
dernier=dernier+2;
}
/*On enregistre le dernier à la fin du fichier*/
fichier = fopen("dernier.txt", "w+");
fseek(fichier, 0, SEEK_SET);
fprintf(fichier, "%d", dernier);
fclose(fichier);
printf("Operation effectuee avec succes.\n");
return EXIT_SUCCESS;
}
/*Renvoi 1 si le nombre est un nombre premier*/
int premier(int test)
{
int nb_premier;
int borne=0;
FILE* fichier = NULL;
fichier = fopen("test.txt", "r+");
if (fichier != NULL)
{
while(feof(fichier)==0 && borne==0)
{
fscanf(fichier, "%d", &nb_premier);
/*printf("%d\n", nb_premier);*/
/*Nombre divisible par un nombre premier,
premier(test)=0*/
if(test%nb_premier==0)
{
fclose(fichier);
return 0;
}
/*Si la racine carré du nombre testé est inférieure au
nombre premier actuel,inutile de continuer le test*/
if(nb_premier>sqrt(test))
{borne=1;}
}
fclose(fichier);
if(borne==1)
{return 1;}
}
return 0;
}
Illustration: illustrer.fr