Algorithme de decomposition en nombre premier
SVP je suis unéléve de 3éme année secondaire en science informatique et je cherche quelqun qui pent m'aider à faire l'algorithme de decomposition en nombre premier par une méthode mathématique optimal comporte ca '6*(n+1)' merci de votre répance.
Configuration: Windows XP Internet Explorer 6.0
3 réponses
-
Salut
Qu'entends-tu par '6*(n+1)' ? Complexité ?
Sinon, il n'existe pas d'algorithmes polynomiales. Les meilleurs algorithmes ne sont pas très performants, ils posent problèmes dès que le nombre à factoriser est grand.
L'algorithme est le suivant :
decompose(Entree : N, Sortie tableau : tableau d'entiers)
variable : i
Pour i de 3 à racine(N) par pas de 2 faire
si i divise N alors mettre i dans tableau et N=N/i
fin Pour
retourne Tableau
finFonction
Tu peux augmenter la vitesse en établissant en mémoire la liste de tous les nombres premiers inférieurs à racine(N). -
Bonjour,
si n = 1
alors premier <-- false { 1 n'est pas un nombre premier }
sinon
nestpasdivisible <-- true { n est premier si et seulement si n }
{ n'est divisible par aucun i }
pour i de 2 à Racine(n) { compris entre 2 et la racine carree de n }
estdivisiblepari <- EstDivisiblePar(n,i)
nestpasdivisible <-- nestpasdivisible and not estdivisiblepari
fin pour
premier <-- nestpasdivisible
fin si -
est ce que c'est une solution recursif
