Algorithme
colas
-
boudjeroua -
boudjeroua -
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
.
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
.
5 réponses
-
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...
. .
\_/ -
-
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..." -
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 ...
-
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
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.
