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
- Premier pro - Télécharger - Montage & Édition
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- En raison d'un nombre important d'échec de connexion snapchat - Forum Snapchat
- Nombre facile - Télécharger - Outils professionnels
- Dans ce fichier, réalisez le graphique xy (nuage de points ou dispersion), avec les x en abscisse. dans le graphique, les points dessinent un nombre. lequel ? - Forum Bureautique
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
