Algorithme de decomposition en nombre premier
Fermé
haithouma
Messages postés
1
Date d'inscription
vendredi 27 avril 2007
Statut
Membre
Dernière intervention
5 mai 2007
-
5 mai 2007 à 19:02
gafi Messages postés 7 Date d'inscription dimanche 16 décembre 2007 Statut Membre Dernière intervention 1 février 2008 - 16 déc. 2007 à 18:27
gafi Messages postés 7 Date d'inscription dimanche 16 décembre 2007 Statut Membre Dernière intervention 1 février 2008 - 16 déc. 2007 à 18:27
A voir également:
- Algorithme de decomposition en nombre premier
- Nombre premier en c - Astuces et Solutions
- Décomposition facteur premier casio graph 35 - Forum calculatrices
- Algorithme qui affiche si un nombre est premier ou pas - Forum Pascal
- Ppcm algorithme - Forum Programmation
- Fonction premier algorithme ✓ - Forum Pascal
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).
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
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
Messages postés
7
Date d'inscription
dimanche 16 décembre 2007
Statut
Membre
Dernière intervention
1 février 2008
4
16 déc. 2007 à 18:27
16 déc. 2007 à 18:27
est ce que c'est une solution recursif