Calcul des nombres premiers inférieurs ou égaux à un nombre donné

(nb: il s'agit plus ici d'un essai de c++ que de mathématiques. Quand au c++, je n'utilise pas d'astuces qui rendent le programme difficile à lire)

kdevelop configuré pour c/c++ sur suse linux 10.0.

Ecrit en c++ pour exécution dans une console.

Pour mettre en œuvre dans kdevelop, c'est simple:

• lancer kdevelop configuré pour c/c++ dans une console
• faire “nouveau projet”
• demander le projet c++: simple hello, avec le nom de projet que vous voulez (nombrespremiers ?), et dans votre zone de travail (/home/toto/developpement par exemple).
• kdevelop vous fabrique alors dans cette zone un répertoire calculdecredit avec tout ce qu'il faut.
• vous placez la partie du code que vous trouvez ci-dessous et qui manque dans le hello.
• la 1ère fois que vous demandez de construire le projet, il fabrique le makefile qui manque.
• si “succès”, demandez l'exécution du programme.
• bon amusement !

On essaye tous les nombres impairs de 3 à nbmax (valeur demandée au début). On divise le nb à essayer par tous les nb premiers déjà trouvés (et qu'on a conservés dans le tableau tabnbp[]), mais on s'arrete à racine de nbmax parce que c'est inutile d'aller plus loin. Pour conserver les nombres premiers trouvés, on créé à la volée (new llint[]) un tableau dans le tas, de taille suffisante pour contenir tous les nb premiers (20% de nbmax, et au moins 1000), et on le détruit à la fin (delete[]).

Sur un pc avec pentium 3 Ghz, et en comptant à partir de “2”:

• pour nbmax=1 million: on trouve 78.498 nombres premiers en moins d'1 sec
• pour nbmax=10 millions: on trouve 664.579 nombres premiers en 12 sec
• pour nbmax=100 millions: on trouve 5.761.455 nombres premiers en 4 mn 12 sec
• pour nbmax=1 milliard: on trouve 50.847.534 nombres premiers en 1h 45'

Développement possible:

• conserver le tableau des nombres premiers sur disque et en calculer le plus possible (calcul sur plusieurs jours ?), la limite dépendant de la longueur de votre “long long int” (8 octets chez moi)
• utiliser le tableau conservé sur disque pour chercher la décomposition d'un nombre en facteurs premiers,
• idem pour dire si un nombre donné est premier ou non (si on a conservé un tableau de taille suffisante, il suffit de chercher dedans par dichotomie),
• etc…

Si on veut traiter des nb plus grands que “long long int”, il faut utiliser des bibliothèques spécialisées comme gmp http://www.swox.com/gmp/ (très très efficace !). Cette bibliothèque est déjà intégrée à la suse 10.0 sous forme de rpm, et le manuel est à chercher dans: konqueror → info:/gmp (j'ai passé du temps à le chercher !).

Code :

/***************************************************************************
 *   Copyright (C) 2005 by Tyrtamos                                        *
 *   tyrtamos@jpvweb.com                                                   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
 
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
 
#include <iostream>
#include <cstdlib>
 
#include <math.h>
#include <time.h>
 
using namespace std;
 
typedef long long int llint;
 
llint *tabnbp;
llint i, imax, nbmax, nb, nbrac, nmaxres;
 
bool premier;
char car;
time_t tps1, tps2;
 
int main(int argc, char *argv[]) {
    do {
        cout << "Calcul des nombres premiers inférieurs à  quel nombre (0=fin) ? ";
        cin >> nbmax; cout << endl;
        if(nbmax>0) {
            nmaxres=nbmax/5; if(nmaxres<1000) {nmaxres=1000;}  // taille du tableau 
            try{
                tabnbp=new llint[nmaxres];
                }
            catch(...){
                cout << "désolé, pas assez de mémoire !" << endl;
                return 1;
                }
            tabnbp[0]=2;
            imax=0;
            time(&tps1);
            nb=3;
            while (nb<=nbmax) {
                nbrac=sqrtl(nb);
                premier=true;
                for (i=0; tabnbp[i]<=nbrac; i++) {
                    if((nb % tabnbp[i])==0) {premier=false; break;}
                    }
                if(premier==true){
                    imax++;
                    tabnbp[imax]=nb;
                    }
                nb+=2;
                }
            time(&tps2);
            cout << endl;
            cout << "Calcul terminé" << endl;
            cout << "Il y a " << imax+1 << " nombres premiers" << endl;
            cout << "Durée du calcul : "; cout << tps2-tps1 << " secondes " << endl << endl;
            cout << "voulez-vous les afficher (O/N)?"; cin >> car; cout << endl;
            if((car=='O') || (car=='o')){
                for(i=0; i<=imax; i++){
                    cout << tabnbp[i] << endl;
                    }
                }
            delete[] tabnbp;
            }
        } while(nbmax>0);
    return EXIT_SUCCESS;
    }