algorithme de decomposition en nombre premier Fermé

Question

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.

Fiddy · Accepted Answer

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).

aminof · Answer

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

gafi · Answer

est ce que c'est une solution recursif

Algorithme de decomposition en nombre premier

3 réponses

Discussions similaires