Inscription / Connexion Nouveau Sujet
Défi sur les nombres premiers
Bonsoir tout le monde,
Je lance une bouteille à la mer.
Je voudrais vous parler d'un défi informatique que je souhaite relever. Il s'agit du dernier cours de système. Le défi est en apparence d'une simplicité enfantine : donner tous les nombres premiers inférieurs à.
Vous avez bien lu : mille milliards.
Mais voilà... gros gros problème. La machine sur lequel le programme sera testée est imposée. Mes camarades et moi pouvons nous connecter dessus et tester à tout moment l'algorithme. Le problème est le suivant : la place mémoire, limité à 4Go. Il s'agit d'une machine virtuelle qu'il est impossible d'améliorer.
Mon premier essai est bien entendu un retentissant échec. Calculer jusqu'à un milliard () ne pose pas de problème, mais la mémoire est quasiment entièrement consommée.
L'algorithme naïf que j'ai est écrit est le suivant :
- Initialiser une liste de nombres premiers : 1, 2, 3, 5. Cette liste appelée LISTE va s'enrichir au fur et à mesure de la recherche.
- Initialiser une variable à 7 : nombre = 7
- Limite =
Algorithme général :
Tant que nombre < Limite
Faire boucle 1
Racine = arrondi_par_exces(racine_carree(nombre))
Parcourir LISTE :
index = 1;
element = LISTE.extraire(index);
Boucle 2
Tant que (element <= Racine ET nombre modulo element != 0)
index = index + 1;
Fin boucle 2
Si (element > Racine)
Alors ajouter element à LISTE
nombre = nombre + 2
Fin boucle 1
Chose importante : la performance n'est pas la priorité. L'efficacité est le seul critère déterminant et non l'efficience. Pour information, Il me faut environ 11 minutes pour trouver tous les nombres premiers inférieurs à un milliard. Il y en a exactement et le plus grand est
. Bon j'arrête le zèle.
Je cherche à diviser chaque nombre impair par la liste connue des nombres premiers. J'arrête la recherche de divisibilité lorsque j'atteins la racine carrée du nombre étudié.
J'ai mis des optimisations : j'élimine tout de suite les multiples de 3 et 5 facilement identifiables. Cela n'influe que la performance.
Je constitue une liste qui s'enrichit... et le programme s'arrête pour manque de mémoire alors que la recherche. En revanche, je dispose d'une très grosse place disque. Je suis libre d'écrire sur disque tout ce que je veux, il n'y a pas de limite.
A titre d'information le fichier contenant les nombres premiers inférieurs à un milliard est quand même d'une taille significative : 450 Mo ! Donc, je réfléchis à un programme qui lit chaque nombre dans le fichier... problème, la lecture du fichier complet prend environ 2 minutes. Pour atteindre l'algorithme étudiera près de 500 milliards de nombres. Puisque je peux vite identifier les multiples de 3 et de 5, il m'en reste près de 250 milliards... 250 milliards que je multiplie par 2 minutes... mouais...
Quelqu'un aurait il une idée, un conseil, une piste ?
Le chercheur qui a lancé ce défi n'a pas indiqué s'il l'a accompli.
Merci par avance.
salut
deux remarques :
1 n'est pas un nombre premier
tu élimines les multiples de 3 et 5 certes mais de toute façon si un nombre (impair) est premier alors il est de la forme à partir de 5
ce qui est beaucoup plus rapide que nombre = nombre + 2
soit on considère une boucle sur k "de 6 en 6 " et on considère nb1 = 6k - 1 et nb2 = 6k + 1 qu'on teste de façon "quasi simultanée (leur racine carrée est quasiment identique et d'autant plus que 6k est grand)
soit on part de 5 et on boucle + 2 puis + 4 puis + 2
donc on part de 5 +2 = 7 + 4 = 11 + 2 = 13 et on teste à chaque fois
il me semble que la première façon sera plus rapide : on ne parcourt qu'une fois la boucle des premiers jusqu'à la racine carrée avec deux tests
plutôt que de parcourir deux fois la boucle des premiers jusqu'à la racine (quasiment identique de 6k - 1 et 6k + 1)
avec des booléens ça se gère facilement
je suis étonné de la taille du fichier (450 Mo) ...
Merci carpediem pour ce calcul que j'ignorais. Tous les nombres premiers sont donc un multiple de 6 auquel on ôte ou ajoute 1.
Quant à la taille du fichier, je vous assure que c'est bien 450 Mo.
Jusqu'à un milliard, nous comptons environ nombres premiers. Le premier nombre premier sur 9 chiffres est
, il est le
ème. Ainsi, près de
des nombres du fichier sont sur 9 chiffres.
Mince, j'ai appuyé par mégarde sur le bouton "Poster".
Je disais donc % des nombres sont sur 9 chiffres auxquels on ajoute le caractère de retour à la ligne, ce qui représente environ 45 millions de lignes à 10 caractères, donc 450 millions d'octets. A cela s'ajoutent environ 40 millions d'octets pour les nombres de moins de 9 chiffres. D'où les 450 Mo, sachant que 1Mo représente très exactement
octets.
merci pour ces info
une dernière question car je ne m'y connais pas trop :
pourquoi dis-tu qu'il y a 45 millions de lignes de 10 caractères ?
à quoi correspond une ligne ? (un nombre premier ?)
merci
Alors, plein de petites choses.
Pour stocker un nombre comme 1234567890 dans un fichier, il te faut 10 octets, plus 2 pour le saut de ligne. Ok.
Parce que tu as choisi de stocker dans un format 'TXT', facilement lisible pour un humain. Si tu veux stocker dans un format lisible par un programme, tu peux écrire de façon un peu plus économique. Tu peux dire que chaque nombre occupe systématiquement la même place (la plus grande place nécessaire, donc 12 chiffres), et ne plus mettre les séparateurs. Tu peux même écrire les nombres en base 256 au lieu de les stocker en base décimale, et tu vas encore réduire sensiblement la taille du fichier.
En gros, tu vas le diviser par 3. Et c'est d'ailleurs le mode de stockage par défaut des programmes un peu sérieux.
Mais peu importe. Je disais tout ça juste pour ta culture, ça ne servira pas pour cet exercice.
Ce fichier avec la liste de tous les nombres premiers, au final, tu as besoin qu'il soit lisible par un humain, donc ne change rien à ton fichier.
Il y a une autre piste d'amélioration à ton travail.
Le fichier, il sert à garder le résultat final de ton programme.
Dans ta 1ère idée, tu as un tableau en mémoire (mémoire limitée), avec la liste de tous les nombres premiers.
Oui, bien.
Mais tu veux chercher tous les nombres premiers jusqu'à 10^12 ""seulement"".
Et pour savoir si un nombre n est premier, tu as besoin d'avoir en mémoire un tableau avec tous les premiers jusqu'à .
Donc ... ....
Je ne finis pas la phrase, à toi de chercher un peu où je veux en venir.
Merci beaucoup carpediem et ty59847 !!
J'avais la solution sous les yeux et ne la voyais pas... Inutile de garder en mémoire les nombres premiers supérieurs à ...
Je pense que je suis suffisamment armé pour aller jusqu'au bout. Je pense même pouvoir aller jusqu'à .
Je pense quand même que cela prendra du temps, je ferai ça plus tard.
Concernant la taille des nombres, je confirme que le caractère de fin de ligne et retour chariot est composé de deux octets.
J'avais donné beaucoup d'indices... et tu as su compléter la phrase.
Tu as ton plan de travail, il n'y a plus qu'à appliquer.
Tout à fait... j'avais les lunettes embuées à force de porter un masque.
Je ferai un retour sur l'algorithme que je développerai :
- charger la liste des nombres premiers jusqu'à : il y en a
en incluant 1, le dernier avant
est
)
- à partir de 5, chercher tous les entiers de la forme et
et on calcule
- un nombre premier identifié est écrit dans un fichier.
Je mettrai des traces pour voir le temps de calcul.
A très vite, j'espère.
Rappel : Carpediem l'a dit, 1 n'est pas un nombre premier !
En mode mauvaise foi :
Je ne l'ai jamais dit... Seulement écrit.
Effectivement, 1 n'est pas premier. Et le pire... je l'avais exclu de la liste.
Bonjour,
Effectivement,si tu as la liste des premiers jusqu'à 999 983 tu peux obtenir la liste
jusqu'au dernier avant 1 000 000 000 000
je pense que le dernier est 999 999 999 977
Même en sélectionnant les candidats ,il faudra du temps et de la place
Bonjour,
Je découvre ce topic.
999 999 999 977 n'est pas premier (divisible par11)
En revanche 999 999 999 989 l'est.
Bonjour,
L'algorithme tourne depuis mardi soir. Au bout de 49 heures de calcul, il a quasiment atteint le palier . Par analogie, il devrait le franchir vers minuit, soit 53 heures... Toujourspar analogie, je table sur 60 heures de calcul pour parcourir la seconde moitié. Près de 120 heures en tout, soit 5 jours... Côté performance, ce n'est donc pas terrible.
Petite bonne nouvelle : l'algorithme consomme assez peu de mémoire, occupant environ 200 Mo.
Cependant, j'ai eu une idée. Il est temps que je fasse de la programmation parallèle. Je m'explique : je peux disposer de 8 machines dans une salle de TP... Sachant que mon programme dispose des nombres premiers jusqu'à et que je lui donne une fenêtre de recherche, je peux simplement découper l'intervalle qui me reste en 8 et le donner à chaque machine. Un simple TP de programmation distribuée.
Annuler
connectez vous