D'abord, j'aimerais préciser que ce n'est pas ma faute si hier soir je n'ai pas écrit de message... Internet m'a abandonné pour toute la soirée! :\ Même à minuit ça ne fonctionnait toujours pas.
Comme je vous ai déjà parlé de Project Euler, je ne vous ferai qu'un bref rappel: il s'agit d'un site où il y a des problèmes mathématiques à résoudre qui requièrent de la programmation, car trop longs à résoudre sinon.
Il y a un problème qui me tenait rigueur, à savoir calculer la somme de tous les nombres premiers inférieurs à 2 000 000. Ce n'est pas tellement difficile à programmer un algorithme -- ce que j'ai fait d'ailleurs. On prend un chiffre, on le divise par tous les entiers naturels entre 1 (inclusivement) et lui-même, et si exactement 2 divisions parfaites se sont produites, c'est un nombre premier. Sinon, non.
L'avantage de faire ça, c'est que c'est un algorithme, c'est-à-dire que ça mène invariablement à la réponse, mais pas nécessairement de la manière la plus courte. Et effectivement, c'est très long. Par exemple, j'avais programmé un tel programme en VBA dans Excel... au total, le programme doit avoir roulé environ 15 heures (je l'ai fait roulé 15 ou 16 fois --- je suis rendu dans la colonne O je pense...), et je ne suis rendu que dans les 700 000. Pas très efficace.
J'ai donc voulu tester mes nouvelles connaissances, acquises en 2 jours seulement, pour me programmer un tel programme en java. Tel que susmentionné, j'ai utilisé l'approche algorithmique, en pensant que ce ne serait pas "trop" long... Le programme a démarré à 18h49 hier soir. Vers les 23h50 (un peu avant je pense), à savoir 5 heures plus tard, le programme terminait enfin... ! Je n'ai pas pu vérifier ma réponse, naturellement, parce qu'Internet ne fonctionnait pas. Mais ce matin, oui... imaginez-vous ces heures perdues si j'ai fait une petite erreur conne dans le code. :\
public class NbPremiers {
public static void main(String[] args) {
double n = 0;
final int LIMITE = 2000000;
for (int i=1 ; i <= LIMITE ; i++) {
int cpt = 0;
boucleJ : for (int j=1 ; j <= i ; j++) {
if ((i % j) == 0) {
cpt++ ;
if (cpt > 2) break boucleJ ;
}
}
if (cpt == 2) { n += i ; }
}
System.out.println (n);
}
}
Ça donne le résultat suivant: 1.42913828922E11, c'est-à-dire 142 913 828 922, ou encore 143 milliards.
... et c'est la bonne réponse! :D
En passant, une manière que le programme aille beaucoup plus vite serait de faire un while où la condition serait que j < cptQuelconque, où on prendrait à chaque boucle cptQuelconque = i / j, avant d'incrémenter j (j++), et où i est le nombre dont nous étudions ses facteurs dans la boucle actuelle. Mais bon... trop paresseux pour faire ça...
Comme je vous ai déjà parlé de Project Euler, je ne vous ferai qu'un bref rappel: il s'agit d'un site où il y a des problèmes mathématiques à résoudre qui requièrent de la programmation, car trop longs à résoudre sinon.
Il y a un problème qui me tenait rigueur, à savoir calculer la somme de tous les nombres premiers inférieurs à 2 000 000. Ce n'est pas tellement difficile à programmer un algorithme -- ce que j'ai fait d'ailleurs. On prend un chiffre, on le divise par tous les entiers naturels entre 1 (inclusivement) et lui-même, et si exactement 2 divisions parfaites se sont produites, c'est un nombre premier. Sinon, non.
L'avantage de faire ça, c'est que c'est un algorithme, c'est-à-dire que ça mène invariablement à la réponse, mais pas nécessairement de la manière la plus courte. Et effectivement, c'est très long. Par exemple, j'avais programmé un tel programme en VBA dans Excel... au total, le programme doit avoir roulé environ 15 heures (je l'ai fait roulé 15 ou 16 fois --- je suis rendu dans la colonne O je pense...), et je ne suis rendu que dans les 700 000. Pas très efficace.
J'ai donc voulu tester mes nouvelles connaissances, acquises en 2 jours seulement, pour me programmer un tel programme en java. Tel que susmentionné, j'ai utilisé l'approche algorithmique, en pensant que ce ne serait pas "trop" long... Le programme a démarré à 18h49 hier soir. Vers les 23h50 (un peu avant je pense), à savoir 5 heures plus tard, le programme terminait enfin... ! Je n'ai pas pu vérifier ma réponse, naturellement, parce qu'Internet ne fonctionnait pas. Mais ce matin, oui... imaginez-vous ces heures perdues si j'ai fait une petite erreur conne dans le code. :\
public class NbPremiers {
public static void main(String[] args) {
double n = 0;
final int LIMITE = 2000000;
for (int i=1 ; i <= LIMITE ; i++) {
int cpt = 0;
boucleJ : for (int j=1 ; j <= i ; j++) {
if ((i % j) == 0) {
cpt++ ;
if (cpt > 2) break boucleJ ;
}
}
if (cpt == 2) { n += i ; }
}
System.out.println (n);
}
}
Ça donne le résultat suivant: 1.42913828922E11, c'est-à-dire 142 913 828 922, ou encore 143 milliards.
... et c'est la bonne réponse! :D
En passant, une manière que le programme aille beaucoup plus vite serait de faire un while où la condition serait que j < cptQuelconque, où on prendrait à chaque boucle cptQuelconque = i / j, avant d'incrémenter j (j++), et où i est le nombre dont nous étudions ses facteurs dans la boucle actuelle. Mais bon... trop paresseux pour faire ça...
4 commentaires:
Une façon encore plus efficace: le Crible d'Ératosthène.
Si tu veux savoir si un nombre est premier, tu n'as qu'à vérifier s'il est divisible par tout les nombres naturels plus petit que sa racine carré.
Par exemple, si tu veux vérifier que 25523 est premier, tu vérifies si les entiers de 2 jusqu'à 158 le divisent.
Je te laisse le soin de prouver que ça fonctionne.
J'ai utilisé cette méthode moi aussi et ça a fonctionné
eh ben... je me coucherai moins niaiseux ce soir!
je viens d'aller sur wikipédia pour lire à propos du "crible d'es..." ... quand même fort! j'aurais dû savoir ça avant, ç'aurait pris beaucoup moins de temps à rouler!
Publier un commentaire