Discussion :

[akorx]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[akorx]

J'oubliais une chose très importante : dois je libérer la mémoire à la fin de mon programme? si c'est le cas par quelle méthode?

[koala01]

Salut,

Pourrais tu déjà essayer de justifier l'utilisation d'un pointeur sur un entier lorsqu'il s'agit d'appeler ta fonction

Pour rappel, un pointeur n'est jamais qu'une variable enitère numérique particulière en cela qu'elle représente... l'adresse ("physique") à laquelle la variable se trouve effectivement.

Comme tu ne modifie absolument pas "ce qui est pointé" par ton pointeur, pourquoi vouloir absolument ajouter une indirection

Ceci dit, il est bon de garder le principe de la responsabilité unique (Single Responsability Principle ) en tête, et donc de veiller à ce que chaque fonction ne fasse qu'une chose, mais qu'elle le fasse bien...

J'aurais donc plutôt tendance à créer une fonction estPremier qui prend effectivement un entier et une référence (constante, pour bien faire) sur un std::vector contenant ceux que l'on a déjà trouvé, et qui renvoie simplement vrai si le nombre recherché est premier et false si ce n'est pas le cas.

Ce serait alors à la fonction main de veiller à insérer le nombre s'il apparait qu'il est, effectivement, premier.

Ta boucle ressemblerait donc plutôt à quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
for (i=2; i<10000000; i++)
    {
        if(estPremier(i,t))
            t.push_back(i);
    }

Pour répondre à ta question quant à savoir si tu dois libérer la mémoire:
La classe std::vector est suffisemment intelligente pour gérer elle-même la mémoire dont elle a besoin.

D'un autre coté, tu n'alloue absolument jamais de mémoire pour le seul pointeur que tu utilise avec new. Il est donc totalement inutile (et dangereux) de libérer l'adresse mémoire vers laquelle il pointe (avec delete).

Le fait que tu te sois posé la question met parfaitement en évidence ce que l'on répète sans cesse : il est important d'éviter le recours aux pointeurs, à moins que l'on n'ait vraiment pas le choix

[akorx]

Je me disais que l'utilisation d'un pointeur (ici Pi) m'éviterais de copier la valeur de i à chaque fois en y faisant plutôt référence (c'est le but du pointeur) pour optimiser légèrement les perfs étant donné que je "jongle" avec cette variable 10 millions de fois...

D'ailleurs je pensais avoir raison de le faire car si on fait le test en utilisant le pointeur mon programme met 20s pour trouver les nombres premiers compris entre 0 et 10 millions alors que sans le pointeur je passe à 78s...

C'est bien dans ce but d'optimisation et de critique que je suis venu vous proposez d'analyser mon code et je pensais justement que le pointeur était l'une des solutions...

Pour résumer : je n'aurais pas utiliser de pointeur et tu m'aurais proposé de le faire je me serais "bon sang c'est clair il a raison c'est bien plus rapide" mais là tu sembles me dire qu'il vaut mieux l'éviter .

Qu'en est il?

[screetch]

erroné;

si tu ne copies pas l'entier i lui même, tu dois copier son adresse. Or une adresse est au mieux, aussi grande qu'un entier; au pire, deux fois plus grande, donc c'est plus coûteux de copier l'adresse.

[screetch]

autre optimisation; lorsque tu fais push_back sur un vecteur, il se peut que le vecteur n'aie plus de place, et du coup tout va devoir être réalloué (ca veut dire, nouvelle allocation mémoire, copie de tooooouuuut le tableau, destruction de la mémoire précédente)

la solution est d'utiliser "reserve" sur le tableau et de réserver assez de mémoire pour contenir tout ce dont tu as besoin. Une sorte de borne supérieure.
Par exemple, sur 10000000 de chiffres, retirer tous ceux qui sont multiple de 2, de 3 et de 5 va elaguer enormément
Multiple2 = 10000000/2 (il y a 1/2 de multiples de deux)
Multiple3 = 10000000/3 (...)
Multiple5 = 10000000/5 (...)

(mais on a retiré trop de chiffres; ceux multiples de 6 sont retirer deux fois, ceux de 10 et ceux de 15 aussi, et ceux de 2*3*5 sont eux retirer 3 fois)
Multiple6 = 10000000/6
Multiple10 = 10000000/10
Multiple15 = 10000000/15
Multiple30 = 10000000/30

Max = 10000000-Multiple2-Multiple3-Multiple5+Multiple6+Multiple10+Multiple15+2*Multiple30
ca fait genre 3166666 (maxi)

bon mes maths sont sans doutes toutes pourries mais c'est l'idée