DÉFINIR LES N PREMIERS NOMBRES 'PREMIER'

Signaler
Messages postés
536
Date d'inscription
mercredi 27 avril 2005
Statut
Membre
Dernière intervention
22 août 2008
-
Messages postés
540
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/32169-definir-les-n-premiers-nombres-premier

Messages postés
540
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2
voila le crible d'eratostene en c je les affiche pas tous mais for(int c;c<50000000;c++)if(tab[c])printf("%d",c);

#include <cstdlib>
#include
#include <math.h>
bool tab[50000000];
using namespace std;
int main(int argc, char *argv[])
{
int a;
for(int i=0;i<50000000;i++)
tab[i]=true;

system("pause");
for(int i=2;i<50000000;i++)
{
if(tab[i])
{
for(a=1;i*(a+1)<50000000;a+=1)tab[a*i]=false;
}
}
printf("fin\n");
system("pause");
return EXIT_SUCCESS;
}
Messages postés
5
Date d'inscription
mercredi 16 février 2005
Statut
Membre
Dernière intervention
10 novembre 2005

Merci pour toutes ces explications, je vais étudier tout ça, et éventuellement mettre une mise à jour en place.
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

d'une manière générale, tu ne dois tester que la division par les nombres premiers inférieurs ou égaux à la racine carrée du nombre que tu testes. autrement dit: si tu génères, avec le crible d'eratosthène, les nombres premiers de 1 à 500 000 000 (c'est vite fait, le problème c'est la mémoire, si tu optimises bien ton algo ça roule), tu peux tester la primalité d'un nombre compris entre 500 000 000 et 250 000 000 000 000 000 en un temps proportionnel à la racine carrée du nombre testé: chouette :). le seul hic: il faut utiliser une classe de gestion des nombres très grands, et c'est plus lent.

si tu ne t'intéresses qu'aux naturels accessibles via un long long int (32 bits sur la plupart des machines), tu ne dois utiliser le crible que sur l'intervalle de 1 à sqrt(2^32) 2^16 65 536 (faut tjs connaître sa table de puissances de 2 :p), et ça c'est fait en moins d'une milliseconde, promi juré ^^.
Messages postés
540
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2
(j'ai oublié d'expliquer regarder bien il y a un code entre /** **/ c'était pour faire la comparaison)
Afficher les 19 commentaires