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/Cribl [...] th%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é) :

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 ?

up

http://www.cppfrance.com/codes/PRO [...] 40808.aspx

Bonjour fluminis, le code de ce lien est un programme qui crée des threads (en utilisant "openmp" ) qui vont faire le calcule en parallèle sur une même machine, ce n'est pas exactement ce que je cherche.

Ce que je veux c'est une version distribué (réparti sur plusieurs machines) de l'algorithme de calcule de nombres premiers. Les processus se trouvant sur les différentes machines communiques entre eux via l'envoi de messages (ça sera via sockets lors de l'implémentation).

Oui, le but de mon lien etait :
- que tu t'inspire de l'algo pour faire ce que souhaite faire
- dire que le Crible d'Ératosthène n'est pas forcement l'algo qu'il te faut si tu fait du multithread, ou alors qu'il faut que tu le modifies...

Merci fluminis,
J'ai rapidement lu le code source du lien mais c'est un peut codé à l'arrache (et en C++), je n'ai pas bien compris son principe, peux tu me le transcrire en Algorithme clairement parlé ?
Sinon pour le Crible d'Ératosthène justement je cherche à le modifié de façon a ce qu'il soi distribué.

euh c plsu du C que du C++ hein

Même pas, ce n'est pas du standard. Enfin peut importe un algo claire et bien fait sans utiliser quelque chose comme openmp serai bien mieux (indépendamment de la spécificité de tel ou tel langage de programmation).

bon tu as surtout envie qu'on fasse ton travail à ta place.  
Les pragma openMP ne changent rien à la sémantique du code qu'ils entourent donc t'as un bete nid de boucle à dépioter.
 
Hint % c'ets modulo

Non, le truc c'est que je ne voudrais pas changé d'algorithme, je voudrais utilisé quand même le Crible d'Ératosthène.

J'ai trouvé quelque chose qui parle de ce que je veux faire (Crible d'Ératosthène version distribué): http://hal.archives-ouvertes.fr/do [...] leRoue.pdf
Mais c'est expliqué juste dans un petit paragraphe j'arrive pas faire le pseudo-code algorithmique.