DÉFINIR LES N PREMIERS NOMBRES 'PREMIER'
MuPuF
Messages postés
536
Date d'inscription
mercredi 27 avril 2005
Statut
Membre
Dernière intervention
22 août 2008
-
20 juin 2005 à 09:38
rrk275 Messages postés 540 Date d'inscription vendredi 25 juin 2004 Statut Membre Dernière intervention 1 octobre 2007 - 10 nov. 2005 à 15:10
rrk275 Messages postés 540 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
https://codes-sources.commentcamarche.net/source/32169-definir-les-n-premiers-nombres-premier
10 nov. 2005 à 15:10
#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;
}
10 nov. 2005 à 02:22
18 oct. 2005 à 18:19
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é ^^.
17 oct. 2005 à 22:50
17 oct. 2005 à 22:49
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...
5 juil. 2005 à 08:27
AU lieu de parcourir tous les nombres de 2 à p pour savoir s'il est premier, il s'uffit de parcourirs de 2 jusqu'à sqrt(p) (racine carrée de p)
A vrai dire si le nombres p est par exemple 200,
sqrt(200) = 14,142
Il s'uffit de chercher s'il est divisible par un nombre compris entre 2 et 14 !!! Au lieu de chercher entre 2 et 200.
Sur de très grand nombres, on voit netement la différence,
Donc dans ce code, il serait préférable de changer le test d'arrêt de la boucle while, du for et du if :
#include <math.h>
......
while ( c <= sqrt(p) )
{
for (c = 2 ; p % c != 0 && c <= sqrt(p) ; c ++);
....
30 juin 2005 à 13:08
30 juin 2005 à 13:06
cela ferait gagner enormement de temps .... (pour des n depassant 10000)
30 juin 2005 à 10:44
Je pensais que "cela excluant les nombres négatifs" relevait de "qui possède exactement 2 diviseurs"
30 juin 2005 à 00:14
29 juin 2005 à 19:49
Sinon, -1 ayant exactement deux diviseurs (-1 et 1), il serait premier...
29 juin 2005 à 11:05
(ça c'est pour le clin d'oeil à tsutomu)
Sinon, la définition valable est: "un nombre premier est un naturel qui possède exactement deux diviseurs."
Ceci excluant 1 et les nombres négatifs.
29 juin 2005 à 10:06
28 juin 2005 à 23:54
et dans mon message précédent, je voulais dire 500 000 000 ;)
28 juin 2005 à 17:41
ma définition : "x est un nombre premier s'il est divisible que par 1 ou par lui meme..."
mais en cherchant un peu j'ai trouvé aussi ta définition.
apparemment il existe plusiseurs écoles et une grosse dispute pour le cas de 2
21 juin 2005 à 22:46
21 juin 2005 à 17:06
moi j'utiliserais aussi une fonction inline pour se genre d'appel car le compilateur peut directement exécuté cette petite ligne ... A moins que tu ne place uniquement le printf( ) dans le if( ), ainsi tu n'as pas besoin de passer par une fonction supplémentaire ...
Peace
20 juin 2005 à 12:01
Définition d'un nombre premier : "entier naturel ayant strictement deux diviseurs"
1 n'a qu'un diviseur, donc non
Mais bon on a tous fait cette erreur au moins une fois :)
Pour affiche j'aurais mis une macro
#define AFFICHE(p) (printf("%d", (p)))
mais bon... c'est du détail...
20 juin 2005 à 09:38
Sinon un truc qui me plait pas c'est l'appel de la fonction affiche. En fait ça ralenti l'algorythme car ya l'appel de la fonction qui se fait pour une ligne ce qui est inutile. Met directement printf ("%d ", premier); au lieu de l'appel de fonction.
Sinon tu peux essayer de mettre inline void affiche (int premier) comme def de fonction, ça devrait faire la meme chose (c'est bien une bonne solution ici ?).
Pour l'interface graphique c'est tjs du console, mais de toute facon, pour ce genre d'algo te fais pas chier ;-) si on regarde il y a beaucoup de prog en mode console, meme si ils sont appellés par des progs win32.
Bon teste de faire ce que je t'ais dis, et good luck cool mouse