#1 Le 03/06/2009, à 16:13
- /b/nt/
RESOLU librairie (En C) et " fonction isPrime "
Salut,
Existe t-il une librairie (En C) contenant un algorithme ou une fonction isPrime répondant si un nombre est premier ou non à coup sûr ?
Merci
Dernière modification par /b/nt/ (Le 07/06/2009, à 23:55)
#2 Le 03/06/2009, à 18:42
- yannzbig
Re : RESOLU librairie (En C) et " fonction isPrime "
Sans répondre à ta question, pourquoi ne pas coder toi-même cette fonction, ou alors la recopier ici par exemple?
#3 Le 04/06/2009, à 00:57
- /b/nt/
Re : RESOLU librairie (En C) et " fonction isPrime "
Sans répondre à ta question, pourquoi ne pas coder toi-même cette fonction, ou alors la recopier ici par exemple?
En fait c'est parce que je cherche un qui soit le plus rapide (pour les grands nombres).
merci de votre réponse
#4 Le 04/06/2009, à 03:13
- Le Farfadet Spatial
Re : RESOLU librairie (En C) et " fonction isPrime "
Salut à tous !
S
une fonction isPrime répondant si un nombre est premier ou non à coup sûr ?
Manindra Agrawal, Neeraj Kayal et Nitin Saxena, Primes is in P.
Ce sont eux qui ont prouvé que le problème de primalité n'était pas, contrairement à ce qu'on pensait, NP-complet et qui ont donné un algorithme à peu près efficace. Cela dit, la connaissance des nombres premiers reste encore au cœur d'un des problèmes du prix du millénaire (http://fr.wikipedia.org/wiki/Problèmes_ … millénaire), plus précisément de l'hypothèse de Riemann, ainsi que de la cryptographie : si tu avances sur le sujet, tu gagneras un million de dollars et sans doute la médaille Fields, ainsi que l'intérêt de la CIA.
En fait c'est parce que je cherche un qui soit le plus rapide
Plus rapide que quoi ? Quel algorithme utilises-tu ? Le crible d'Ératosthène ? Encore aujourd'hui, les algorithmes les plus rapide utilisé sont probabiliste : ils vont donner une certaine probabilité pour que le nom soit premier.
À bientôt.
Le Farfadet Spatial
Hors ligne
#5 Le 04/06/2009, à 13:10
- Le Farfadet Spatial
Re : RESOLU librairie (En C) et " fonction isPrime "
Salut à tous !
Je reviens à la charge. Tu trouveras des éléments sur le test de primarité et l'algorithme de Miller-Rabin dans l'ouvrage suivant :
Introduction à l'algorithmique
Thomas H. CORMEN, Charles E. LEISERSON, Ronald L. RIVEST et Clifford STEIN
Dunod
À bientôt.
Le Farfadet Spatial
Hors ligne