Salut à tous !

Voilà, je commence à poster des petits exercices d'algorithmique.

Le premier exercice (tiré du Project Euler) :

Énoncé du problème :
La somme des nombres premiers qui ne dépassent pas 10 est 2 + 3 + 5 + 7 = 17
Trouvez la somme de tous les nombres premiers qui ne dépassent pas deux millions.

P.S : Le programme ne doit pas dépasser une minute de calcul.

Je vous laisse réfléchir un peu avant de mettre la solution proposé par moi !

A+

"P.S : Le programme ne doit pas dépasser une minute de calcul. "
Une minute sur quelle machine ?

Deux millions, ce n'est pas beaucoup, une methode classique doit marcher. Crible d'Eratosthene ?

"Une minute sur quelle machine ?"
Peu importe toutes les machines de nos jours se ressemblent !

"Crible d'Eratosthene ?"
Oui. Voyons ton implementation !

"Peu importe toutes les machines de nos jours se ressemblent ! "
Non, elles ne se ressemblent pas. Dans mon bureau j'ai un eeepc, un AMD a deux voies et un quad coeur d'intel.
Je ne te parles meme pas du cluster de d'amd bi coeur, des playstation 3 ou encore des noeuds graphiques.

Non, les machines ne se ressemblent pas et surtout de nos jours.

"Oui. Voyons ton implementation !"
Je n'en ai pas vraiment le temps.
Dans l'idee, tu peux encadrer le plus grand nombre premier de ta suite en te rapellant que les nombres premiers sont peu denses dans N. Dans [1;n], il y a de l'ordre de n/log(n) nombre premiers. La valeur du n ieme nombre premier est de l'ordre de n log(n). Avec ca tu as une bonne approximation du plus grand nombre, ce qui permet de borner le crible intelligement.

Pour aller jusqu'a 2 millions, la somme ne passera probablement pas le million. Donc le tableau du crible fera probablement moins de 4 Mo. En fonction de la machine, on rentre dans le cache. Donc probablement pas la peine de se faire chier a optimiser les access a la ram.

$ time ./euler
sum: 571415680240

real 0m0.019s
user 0m0.020s
sys 0m0.000s

Avec une implémentation très naïve en C à base de crible de crible d'Eratosthène. Et il faut à peine 5s pour faire la somme des nombres premier jusqu'à cent millions (6079462379420972) donc ça n'a pas l'air très critique comme problème. En fait, je pensais que ça serait nettement plus long, sinon je ne me serais pas ennuyé à écrire ça en C.

http://repository.quare.fr/C/euler.c

dnob, exactement ce que je voulais dire en disant 'ca rentre dans le cache'. A peu de chose pres tu es limite par la puissance du CPU.

Une estimation rapide pour 1 million.
Il y a de l'ordre de 1 million /log(1 million) de nombre premier.
ce qui fait de l'ordre de 80 000 nombre premier.
En suppossant que pour chaque on fait un million d'operation pour remplir le crible (sacahnt qu'on en fait beaucoup moins). 80 * 10^9 operations. avec une machine a 1 Ghz, ca fait 80 secondes (rappel, pas de probleme de cache).
Sachant que mon estimation est large, le probleme est simple.

Bon, l'implémentation la plus débile qui existe (en mathematica) :
Timing[Total[Select[Range[2000000],PrimeQ]]]

{1.34808, 142913828922}

mets 1.4 secondes à calculer et me donne un autre résultats : 142913828922

C'est ce qui arrive quand on veut jouer avec des bits en C : on fait des erreurs (cela dit, comme il doit s'agir de plus ou de moins 1 par endroit, ça ne doit pas changer le temps de calcul).

bon pour info, la boucle naive (de 1 a sqrt(n)), me permet de calculer la somme en 10 secondes sur ma machine...

Voilà ma première solution (Une boucle naive). Elle met 6 secondes pour trouver le résultat :

int i = 0, k = 1, n = 0, tab[150000] = {1}, m = 0;
double s = 0;
for (i = 0 ; i < 2000000 ; i++)
{
for (k = 0 ; tab[k] != 0 && tab[k] <= sqrt(i) && n <= 2 ; k++)
{
if (i % tab[k] == 0)
n++;
}
if (n == 1)
{
tab[m] = i;
m++;
s += i;
}
n = 0;
}
s--;
printf("%lf\n", s);

Ma deuxième solution (utilisant le Crible d'Eratosthene). Elle met 0.234 secondes pour trouver le résultat :

1. include <stdio.h>
2. define LEN 2000000

int sieve[LEN];

int main(void)
{
int i, j;
double sum = 0;

for (i = 0; i < LEN; ++i)
sieve[i] = 1;

for (i = 2; i < LEN; ++i)
{
if (1 == sieve[i])
{
sum += i;
for (j = 2 * i; j < LEN; j += i)
sieve[j] = 0;
}
}
printf("%.0lf\n", sum);
return 0;
}

Bon, quand j'ai dit une minute, c'est parce que le Project Euler (duquel est tiré l'exercice) propose de trouver le résultat en un temps qui ne dépasse une minute. C'est tout !

Désolé pour l'indentation !
JV ne prend pas en compte les espaces !

_Nin-jutsu_ > wall ton code http://wall.deblan.fr

Merci As_Pique

Voilà les codes (bien qu'il n'y a pas une coloration syntaxique pour le langage C, je me suis servi de celle du Python) :
http://wall.deblan.fr/1237299158/python/1/
http://wall.deblan.fr/1237299433/python/1/

La vache je viens sur la première fois sur ce forum et je comprends que dalle vous vous y connaissez les gars

Si on part dans les exos algorithmiques du projet Euler, autant en choisir au niveau des ténors du forum .

J'en ai un sympa :
http://projecteuler.net/index.php?section=problems&amp;id=178

-------Texte Original -------
Consider the number 45656.
It can be seen that each pair of consecutive digits of 45656 has a difference of one.
A number for which every pair of consecutive digits has a difference of one is called a step number.
A pandigital number contains every decimal digit from 0 to 9 at least once.
How many pandigital step numbers less than 10^(40) are there?

---------Traduction----------
Considérons le nombre 45656.
On peut remarquer que chaque paire de chiffres consécutifs a une différence de 1. Un tel nombre est appelé step number.
Un nombre pandigital (en base 10) contient au moins une occurence tous les chiffres de 0 à 9.
Combien existe-t'il de pandigital step numbers inférieurs à 10^(40) ?

ah, un probleme de comptage. Ca c'est rigolo! mais ca n'a pas l'air tres complique. Je tente une reponse ce soir !

On peut remarquer qu'il y a forcément une suite de 0 à 9 ou de 9 à 0 dans l'écriture du nombre (par déduction de la propriété step, on ne peut pas aller de 0 à 9 sans passer par tous les chiffres), donc c'est minoré par 2*(10 parmi 40).

Il y a plien de propriete rigolote. Ca me fait penser a de la marche aleatoire.
La premiere question a se poser est combien il y a de possibilite une fois que l'on a rempli la propriete "pandigital". En bref, combien y a t'il d'ecriture step a x nombre en partant du nombre k. Ca s'ecrit bien en programmation dynamique.
Une fois que tu sais calculer ca.
Tu n'as plus qu'a compter le nombre de facon de remplir exactement la propriete pandigital (c'est a dire que sans le dernier chiffre, elle n'est pas rempli). Un tel nombre fini forcement par 0 ou 9, ce qui permet de raccrocher ta propriete.

Il faut juste faire attention, parceque l'on va compter des nombres plusieurs fois. Mais ca donne une borne sup facil.

Ah, et sinon, après une courte recherche infructueuse sur "combinaison+latex", j'ai trouvé comment on codait ce fameux signe : C_40^10