algorithme Fermé

Question

Bonjour,

je cherche un algorithme permettant de tester la primalité d'un nombre entier. J'ai pensé à faire une boucle qui évalue les restes des divisions du nombre à tester par les nombres premiers successifs, inférieurs à 1/2 du nombre à tester, mais je pense qu'il doit exister une méthode plus efficace. Par exemple, sur la calculatrice TI-89, il y a une fonction isPrime() qui fait ce bouleau en un rien de temps, seulement j'ignore comment ça marche.

Merci d'avance si vous pouvez me renseigner

.

teebo · Answer

Il est possible qu'il y ai un tableau, sinon, ce n'est pas jusqu'a un demi, mais jusqu'a racine qu'il faut tester deja, et ca accelere les choses...J'ai plus les autres possibilites en tete...
Bonne chance...
. .
\_/

0BER0N · Answer

salut,regarde par ici: http://www.nist.gov/dads/HTML/sieve.html a+

blux · Answer

Salut,

tu peux essayer le test de Fermat (il n'a pas fait qu'un théorême...:

http://dept-info.labri.u-bordeaux.fr/~betrema/deug/poly/premiers.html

Monsieur veut se lancer dans le reverse engineering de RSA ? ;-)

A+
Blux

"Les cons, ça ose tout.
C'est même à ça qu'on les reconnait..."

vyrteban · Answer

en tout cas, c'est certainement pas à la moitié du nombre que tu dois t'arreter, mais bien à sa racine carrée, vu que tu fais une division et pas une soustraction ...

boudjeroua · Answer

Salut,
Votre idée c'est la bonne idée, car j'ai réussi à le résoudre de la façon Ste:
DEBUT
lire(N)
s=0
pour i=1 à N-1 faire
si N mod i =0 alors
i=i+1
Fsi
Fpour
si i=1 alors
afficher(N,' est 1 nbre premier')
sinon
afficher(N,' n''est 1 nbre premier')
Fsi
Fprog
pour la fct que vous avez trouver sur la calculatrice elle travail avec le même raisonnement; la lécture du nbre N avant l'appel de la fction isprimary() qui a comme paramètre N;
Fonction isPrimary(n:entier):type de la fct que je crois logique (T ou F) c.à.d vraie ou faux.
Merci.

Algorithme

5 réponses

Discussions similaires