Optimisation de vitesse et correction syntaxique
Salut à tous et à toutes !
Je n'ai pas fait de c et de c++ depuis l'école pour ainsi dire (il y a donc une bonne quinzaine d'années) et pour m'y remettre, je viens de m'amuser à écrire un petit programme me permettant de trouver tous les nombres premiers compris entre 2 et 10.000.000 et j'affiche au final le plus grand.
Voici le code que j'ai créé (j'utilise code::blocks).
main.cpp :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <iostream>
#include <ctime>
#include <vector>
#include "verifPremier.h"
using namespace std;
int main()
{
int i(0);
int *Pi=&i; //pointeur sur i
vector<int> t; //tableau dynamique contenant les nombres premiers trouves
t.push_back(2);
long H;
time(&H);
cout << "Heure de lancement = " << ctime(&H) << endl;
for (i=2; i<10000000; i++)
{
siPremier(Pi,t);
}
time(&H);
cout << "Heure de fin = " << ctime(&H) << endl;
cout << "Plus grand nombre premier trouve = " << t.back() << endl << endl << endl << endl << endl;
return 0;
} |
verifPremier.h :
Code:
1
2
3
4
5
6
7
8
9
|
#ifndef VERIFPREMIER_H_INCLUDED
#define VERIFPREMIER_H_INCLUDED
using namespace std;
void siPremier(int *Pi , vector<int> & t );
#endif // VERIFPREMIER_H_INCLUDED |
verifPremier.cpp :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
#include <cmath>
#include <vector>
#include "verifPremier.h"
using namespace std;
void siPremier(int *Pi , vector<int> & t )
{
int taille=t.size();
int i=0;
int j=0;
double racine=sqrt(*Pi);
while (t[i]<=floor(racine) && i<=taille && j==0)
{
if (*Pi%t[i]==0)
{
j++;
}
i++;
}
if (j==0)
{
//cout << *Pi << endl;
t.push_back(*Pi);
}
} |
Pour résumer en gros la méthode que j'utilise pour vérifier si un nombre est premier, je vérifie si il est divisible par les n nombres premiers inférieurs à sa racine carrée. Dès que je trouve qu'il est divisible par l'un d'entre eux je passe au suivant : c'est ce que je fais dans le :
[I]
if (*Pi%t==0)
{
j++;
}
Si le nombre est premier je l'ajoute à mon tableau dans un tableau dynamique ("vector <int> t") ce qui fait que mon tableau évolue comme ceci à chaque incrémentation de i si ce dernier est un nombre premier :
2
2 3
2 3 5
2 3 5 7
2 3 5 7 11
2 3 5 7 11 13
2 3 5 7 11 13 17
2 3 5 7 11 13 17 19
2 3 5 7 11 13 17 19 23
2 3 5 7 11 13 17 19 23 29 .
2 3 5 7 11 13 17 19 23 29 31
2 3 5 7 11 13 17 19 23 29 31 33
2 3 5 7 11 13 17 19 23 29 31 33 37 ...
NB : La méthode de calcul n'est peut être pas la plus rapide pour vérifier si un nombre est premier mais vous l'aurez bien compris : ce n'est pas trop via la méthode que je veux optimiser mon programme mais plutôt par les techniques utilisées (c'est donc purement dans un but pédagogique et non scientifique).. je veux donc juste vérifier si SYNTAXIQUEMENT parlant on peut faire beaucoup mieux (avec des pointeurs par exemple ou autres "techniques" ou objets).
On pourrait peut être ajouter pendant le calcul une petite animation qui bascule entre les symboles du type / -- \ | comme on le voit souvent.
Merci d'avances pour toutes vos réponses, remarques et critiques.
