(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:
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”:
Développement possible:
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; }