Formule de Minac

[Ptimatheu]

Bonjour, voilà après quelques recherches sur le web concernant les nombres premiers, je suis tombé sur une formule (celles de Minac et Willans) qui fournit tous les nombres premiers dans l'ordre et sans répétition.

Malgré cela il est dit qu'elle est inutilisable.... mais pourquoi? A cause de sa complexité, mais avec des supercalculateur qui peuvent atteindre le pétaflops de puissance ne serait-ce pas possible?

Merci de m'éclairer...

[miikou]

salut,
Si tu as essayer de calculer Pn avec cette formule tu as du voir que c pas simple quand meme ^^.
Quand tu dis qu'elle inutilisable, c'est dans quel sens ?

[Ptimatheu]

C'est pas moi qui dit qu'elle est inutilisable, et c'est sa que j'aimerais comprendre.

[leon1789]

Je viens de prendre connaissance de la formule ... A priori, elle demande au moins 2^n additions (de nombres réels !) pour obtenir le n-ième nombre premier. Donc pour n=1000, c'est pas la peine d'essayer !

[Sam Mar]

Bonjour,

oui, si on a besoin de 2^n opérations pour calculer le nième terme, alors on a à faire à un problème NP-complet, c'est donc réalisable pour le petit nombre, mais ça devient vite inimaginable pour même pour n'importe quel supercalculateur.

[ThSQ]

alors on a à faire à un problème NP-complet

Mmmm, sans vouloir pinailler le "alors" me parait pas correct.

Présenté comme ça le calcul est non-polynomial mais rien ne prouve qu'il est NP, et a fortiori NP-complet (sans parler que NP se rapporte à des problèmes de décision).

[leon1789]

Pour mémoire, et , obtenu instantanément par tout bon logiciel de calcul (mais pas avec la formule précitée :happy2: ).

[charif]

bj

je pense que la formule et fausse .car jusq'au aujourdhui on conné pas quand apparaitra le prochain nombre premier....la répartition des nombres premiers est inconnue ...il ya des recherches qui utilize les zéros de la fonction zéta de riemann....ils sont lié a la répartition des nombres premiers dans l'ensemble des nombres entiers naturels