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