DÉFINIR LES N PREMIERS NOMBRES 'PREMIER'

Messages postés
536
Date d'inscription
mercredi 27 avril 2005
Statut
Membre
Dernière intervention
22 août 2008
- - Dernière réponse : rrk275
Messages postés
542
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
- 10 nov. 2005 à 15:10
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

rrk275
Messages postés
542
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;
}
CoolMouse
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.
cs_Kirua
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é ^^.
rrk275
Messages postés
542
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)
rrk275
Messages postés
542
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2 -
je pense qu'on pourrait faire p+=2 simple commodité permettant de tester que les pairs ...
a quoi sert le m ???
/**#include <cstdlib>
#include
#include <math.h>
using namespace std;
int main(int argc, char *argv[])
{
int i = 0, // Incrémenteur définissant le nombres de Premiers trouvés
c = 2, // Variable d'utilisation d'opération
m = 2, // Résultat de l'operation Modulo (%)
p = 10000001 ; // Incrémenteur définissant les nombres susceptibles d'être Premier

for (i = 3 ; i <= 2000000 ; i ++)
{
m = 2 ; // Initialisation des variables
p ++ ;
while ( c != p )
{
for (c = 2 ; p % c != 0 ; c ++);
if (c == p) printf("%d\n",p); // Affiche le nombre premier trouve
else p ++;
}
}
system("PAUSE");
return EXIT_SUCCESS;
}
*/


#include <cstdlib>
#include
#include <math.h>
using namespace std;
int main(int argc, char *argv[])
{
int i = 0, // Incrémenteur définissant le nombres de Premiers trouvés
c = 2, // Variable d'utilisation d'opération
m, // Résultat de l'operation Modulo (%)
p = 10000001 ; // Incrémenteur définissant les nombres susceptibles d'être Premier

for (i = 3 ; i <= 2000000 ; i ++)
{
m = 2 ; // Initialisation des variables
p +=2 ;m=sqrt(p);
c=0;
while (c <m)
{
for (c = 2 ; p % c != 0 && c <= m; c ++);
if (c > m)printf("%d\n",p); // Affiche le nombre premier trouve
else {p +=2;m=sqrt(p);}
}
}
system("PAUSE");
return EXIT_SUCCESS;
}

voici le code transformé m sert a stocker sqrt cela permet de ne pas le recaluler a chaque fois vous verrez je crois avoir (en reprenant les differents coms) multiplié par 10 la vitesse a petite valeur et par 10000 pour des valeurs plus grandes faites le test !! j'ai laissé la vielle version...