Salut à tous,
 
Est ce que quelqu'un saurait ou est ce que je peux trouver des codes sources en C/C++ implémentants des générateurs de nombres premiers?
 
Merci
 
Axel

Aucune idée mais tu peux le faire toi même en implémentant le crible d'ératostène (un conseil fait le en assembleur c bien + rapide)

c quoi le crible d'erastotène !?

Salut...
Le crible d'Erathostène, c'est un algo de détermination des nombres premiers.
Le principe :  
Tu prends un ensemble d'entiers qui se suivent (de 2 à max) puis tu enlèves de l'ensemble les nombres ayant 1 diviseur, en partant du + petit jusqu'au + grand. A la fin, les nbres qui restent sont premiers.
Ex :  je prends les nbres de 2 à 100.
J'enlève les nbres qui ont pour diviseur 2, puis 3, puis 5, puis...
Ya eu 1 post sur ce sujet ya quelques mois.
Pour les nombres de 1 à n, le diviseur max est l'entier immédiatement inférieur à racine de n.
 
Aparté : savez-vous qu'Erathostène, qui savait que la terre était ronde, avait calculé que sa circonférence était d'environ 40.000 km, & ce ya plusieurs milliers d'année ?

Ben oui mais le crible c'est bien quand t'as un nombre maxi d'éléments..
Un truc mieux, c'est de parcourir les nombre entier (jusqu'à ce que t'en aies marre) et de sauver les nombres que tu trouves dans une liste au fur et à mesure.
 
Quand t'as le nombre n, pour tester s'il est premier, tu vois si le reste de la division avec le premier nombre de la liste et nul ou pas. Si oui, tu passes à n+1. Sinon tu passes au nombre premier suivant dans ta liste jusqu'à arriver à la racine carrée du nombre n. Parce que si tu ne trouves pas de multiple à ce moment là, ton nombre est premier.
 
C'est un peu comme le crible d'ératostène mais pas limité (et la racine carrée aide un peu).

c'est cool le gars, mais je ne veux pas réinventer la roue!!
Il est certain que l'on peut trouver un code déjà fait...J'ai tellement de choses à coder que si je pouvais gagner du temps en trouver un générateur de nombres premiers déjà implémenté ce serait terrible...

1 - tu vas sur google  
2 - tu cherches "crible eratostène source"  
3 - tu as trouvé....

J'avais oublié d'indiquer que c'était un générateur de nombres premiers aléatoires que je cherche...Et ca, à vrai dire, je ne l'ai pas trouvé, même sur google...(et pourtant j'ai suivit la méthode de recherche de remittent...)

Bah, un générateur de nombres premier aléatoire, c'est un peu un truc de fou....je crois qu'il y a très peu de manières de calculer des nombres premiers...et qu'elles doivent toutes être très connues, donc, ta série ne ser pas aléatoire longetmps (genre pour du chiffrement, tu oublies)..
Sinon, je connaît un générateur aléatoire de nombre pas premiers!!
n = random();
p = random();
return nxp
 
et ça marche à tous les coups!!

Ce que tu veux, c'est un générateur aléatoire de nombre premiers ou un générateur de nombres premiers aléatoires ?  
Reprenons :
Si tu veux prendre un nb premier au hasard dans une liste de nombres premiers, t'as qu'à prendre 1 entier au hasard, disons l'entier eraThosthene, puis prendre l'erathostenième nombre premier.
Si tu veux prendre 1 nb au hasard puis vérifier qu'il est premier, c'est également très simple.
 
De toute façon, tu couperas pas aux routines de vérification qu'un nb est premier ou à l'énumération de n nombres premiers.

instantdharma a écrit a écrit : Ce que tu veux, c'est un générateur aléatoire de nombre premiers ou un générateur de nombres premiers aléatoires ?   Reprenons : Si tu veux prendre un nb premier au hasard dans une liste de nombres premiers, t'as qu'à prendre 1 entier au hasard, disons l'entier eraThosthene, puis prendre l'erathostenième nombre premier. Si tu veux prendre 1 nb au hasard puis vérifier qu'il est premier, c'est également très simple.   De toute façon, tu couperas pas aux routines de vérification qu'un nb est premier ou à l'énumération de n nombres premiers.

 
n étant le nombre maxi de nombre que tu veux obtenir...
 
C'est clair qu'avoir une table (pré-calculée) ou une liste (dynamique) et ensuite prendre aléatoirement un nombre là dedans ca sera bcp plus simple et rapide. Ca m'étonnerai que t'aies un range infini pour le nombre que tu veux (dans le cas contraire il te faudra soit de la mémoire infinie, soit du temps infini).