Discussion :

[tomap3]

Salut

Je voudrais faire une application réparti sur deux ou plusieurs machines pour le calcule des nombres premiers. J'ai vu qu'il y avais l'algorithme de Crible d'Ératosthène: http://fr.wikipedia.org/wiki/Crible_...atosth%C3%A8ne
mais je ne vois pas comment l'appliquer pour un calcule distribué sur deux machines, vu qu'il n y pas de mémoire commune contenant le tableau.
Avez vous des idées sur comment faire svp ?
Merci d'avance.

Voici l'algorithme (code C) de crible d'Eratosthène en séquentiel (non distribué) :

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
void premiers(int tableau[], long tailleTableau)
{
   long i, j;
 
   tableau[0] = tableau[1] = 0;
   for (i = 2 ; i < tailleTableau ; i++)
      tableau[i] = 1;
 
   for (i = 2 ; i < sqrt(tailleTableau) ; i++)
      if (tableau[i])
         for (j = i*i ; j < tailleTableau ; j += i)
            tableau[j] = 0;
 
   /*Affichage :
   for (i = 0 ; i < tailleTableau ; i++)
      if (tableau[i]) printf ("%ld ", i);
   Fin Affichage */
}

EDIT:
Pour pouvoir répartir le calcule sur plusieurs processus (ce trouvant sur des machines différentes) j'ai pensé à considérer un processus maître qui envoi au autres processus esclaves leur intervalles de calcule (la suite de nombres sur lesquels le processus exécutera l'algorithme) et ce processus maître a lui aussi son intervalle de calcule.

Mais même comme ça ce n'est évident car l'algorithme de calcule des nombres premiers que va effectué un processus P1 sur le 1er intervalle de nombres va avoir un impacte sur le reste des nombres (voir l'algorithme de Crible d'Ératosthène) et donc les calcules du processus P2 par exemple pourront être fausse car peut être P1 a éliminé un nombre (non premier) appartenant à l'intervalle de calcule de P2 mais P2 va quand même effectué le calcule sur ce nombre car il n'as pas été informé par P1.

Vous pouvez peut être me dire dans ce cas de faire en sorte qu'à chaque fois qu'un processus élimine un nombre (non premier), il envoi un message au autres processus (ou au processus concerné) afin les informé que ce nombre est non premier pour qu'ils ne le traitent pas. Mais le problème dans ce cas serai: si le processus P2 (par exemple) a déjà traité le nombre en question avant qu'il ne reçoi le message provenant de P1 lui disant de ne pas le traiter (car non premier).

Des idées pour régler ces problèmes svp ?

[Zavonen]

Eratosthene, me parait difficilement parallélisable.
Atkin par contre (voir wiki) ou mon cours:
Nombres-->naturels-->exercices-->>programmation -->atkin
l'est sans doute (voir les 3 if successifs dans la solution python).
http://perso.univ-rennes1.fr/antoine...51_088_096.pdf

[lakkarin]

Bonjour,

Si je participe à ce forum, c'est seulement pour attirer l'attention aux developpeurs que vous êtes, que j'ai vu qu'il y a un Crible sur un autre forum qui s'appelle " CRIBLE DE LACHKAR" sur le forum de Bibm@th / nombres.
Peut être que crible est rapide que celui d'Eratosthene.
Il faut l'essayer pour juger.

Salut

[alex_pi]

Bonjour,

Si je participe à ce forum, c'est seulement pour attirer l'attention aux developpeurs que vous êtes, que j'ai vu qu'il y a un Crible sur un autre forum qui s'appelle " CRIBLE DE LACHKAR" sur le forum de Bibm@th / nombres.
Peut être que crible est rapide que celui d'Eratosthene.
Il faut l'essayer pour juger.

Salut

C'est bien de se balader de forum en forum pour faire la pub pour un crible inexistant, mais ce serait peut être un peu mieux de le décrire sérieusement, d'en proposer une implémentation et de montrer en quoi il est plus efficace que celui d'Eratosthène hein...

[lakkarin]

C'est bien de se balader de forum en forum pour faire la pub pour un crible inexistant, mais ce serait peut être un peu mieux de le décrire sérieusement, d'en proposer une implémentation et de montrer en quoi il est plus efficace que celui d'Eratosthène hein...

Bonjour,

Si je me balade d'un forum à l'autre, c'est pour rester toujours en contact avec du nouveau.
En ce qui concerne Le Crible de Lachkar, d'après ce que j'ai vu sur le Forum de Bibmath, il s'agit bien d'un Crible qui se compose de 5 colonnes et N-1 lignes.

Il se présente comme di-dessous :


1 2 3 4 5
0 1 3 5 7 9
1 6 8 10 12 14
2 11 13 15 17 19
3 16 18 20 22 24
4 21 23 25 27 29
5 26 28 30 32 34


Donc on peut facilement commencer par l'élimination de certaines colones, lignes en les barrant horizontalement, verticalement ou diagonalement .

la colonne 3 c'est les multiples de5
les lignes impaires sont les nombres impairs,
les multiples de 3 sont les diagonales de droites vers la gauches,
les multiples de 7 sont les diagonales de gauches vers la droite..

Donc, on procèdant de cette façon, il nous ne reste que les nombres premiers.

Sur le Forum en question, ils ont commencer à faire des essais de programmations.

Salut

[alex_pi]

En ce qui concerne Le Crible de Lachkar, d'après ce que j'ai vu sur le Forum de Bibmath, il s'agit bien d'un Crible qui se compose de 5 colonnes et N-1 lignes.

Il se présente comme di-dessous :

Code :

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

1
2
3
4
5
6
7
8
 
	1	2 	3	4	5
0	1	3 	5	7	9
1	6	8	10	12	14
2	11	13	15	17	19
3	16	18	20	22	24
4	21	23	25	27	29
5	26	28	30	32	34

Donc on peut facilement commencer par l'élimination de certaines colones, lignes en les barrant horizontalement, verticalement ou diagonalement .

la colonne 3 c'est les multiples de5
les lignes impaires sont les nombres impairs,
les multiples de 3 sont les diagonales de droites vers la gauches,
les multiples de 7 sont les diagonales de gauches vers la droite..

C'est incompréhensible là ton explication... Et puis bon, s'appuyer sur une représentation graphique, c'est peut être bien à la main, mais pour le programmer, ça ne sert à rien... Parcourir une diagonale pour supprimer les multiple de 7, ça n'a aucune chance d'être plus rapide que de faire une boucle en incrémentant l'indice de 7 à chaque fois. Sans compter le temps passé à construire le tableau initialement alors que pour le crible d'Eratosthène c'est trivial.

Et puis bon, j'attends avec angoisse la représentation graphique des multiples de 163...

Et accessoirement, tu n'as pas 2 et 4 dans ton tableau. Autant le second, ce n'est pas bien grave, autant le premier, pour récupérer tous les nombres premiers sans qu'il soit là, c'est un peu mal barré...

Bref, c'est mal barré ton "crible de Lachkar"