A voir également:
- Comment trouver le facteur premier d'un nombre
- Trouver adresse mac - Guide
- Comment trouver le mot de passe wifi sur son téléphone - Guide
- Trouver un film sans le titre - Télécharger - Divers TV & Vidéo
- Comment trouver le code verrouillage d'un telephone - Guide
- Comment trouver son adresse ip - Guide
4 réponses
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
Ambassadeur
1 568
Modifié le 9 févr. 2020 à 10:39
Modifié le 9 févr. 2020 à 10:39
bonjour, je pense qu'il est inutile, dans le test de primalité, d'aller jusqu'à la moitié du nombre.
par ailleurs, si tu cherches le plus grand facteur premier, pourquoi les cherches-tu tous?
de toutes façons, je pense que ton approche est totalement inefficace.
combien de temps as-tu réfléchi au problème avant de commencer à programmer? programmer ne devrait pas empêcher de réfléchir.
comment chercherais-tu les facteurs premiers d'un nombre, uniquement avec une feuille et un crayon? trouve une méthode efficace, et, ensuite, programme-là.
par ailleurs, si tu cherches le plus grand facteur premier, pourquoi les cherches-tu tous?
de toutes façons, je pense que ton approche est totalement inefficace.
combien de temps as-tu réfléchi au problème avant de commencer à programmer? programmer ne devrait pas empêcher de réfléchir.
comment chercherais-tu les facteurs premiers d'un nombre, uniquement avec une feuille et un crayon? trouve une méthode efficace, et, ensuite, programme-là.
Utilisateur anonyme
Modifié le 9 févr. 2020 à 10:20
Modifié le 9 févr. 2020 à 10:20
Bonjour
d'abord pour présenter correctement un code, voir ce petit tuto https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code
Ensuite, la recherche de nombre premier est toujours très longue.
On appelle ça un crible, tu en trouveras plusieurs sur le net, notamment chez "nous" en C
https://codes-sources.commentcamarche.net/source/s/crible/last William VOIROL s'en est fait une spécialité.
Si on en croit ses commentaires, le cible segmenté de Kim Wallisch serait un des (le?) plus rapide. Il a même écrit une page avec les résultats de ses tests.
http://www.william-voirol.ch/Prog/Maths/Prime/
Ensuite tu cherches le plus grand facteur premier, mais tu commences par 2, c'est le plus petit... et surtout, tu testes tous les nombres.
Moi je ferai une liste (un crible) de tous les nombres premiers entre 2 et nb/2 et je ne testerai la division que de ces nombres. Ainsi le test de primalité n'est fait qu'une seule fois, et le nombre de divisions est très fortement limités.
Après d'instinct, je commencerai par tester la division avec le nombre le plus grand, puis le plus grand restant etc... mais sans garantie d'optimiser la vitesse d'exécution. En effet, il y a des nombres très grands dont le plus grand facteur premier est très petit.
Par exemple pour 2^1000, c'est 2.
Mais l'avantage de commencer par le plus grand c'est que le premier facteur trouvé est aussi le plus grand. Donc on ne continue pas à chercher. Empiriquement je pense qu'il y a plus de cas où c'est un avantage qu'un inconvenient.
Enfin, si tu dois chercher le plus grand facteur de plusieurs nombres, garde la liste de nombres premier et complète là au fur et à mesure si besoin.
Par exemple premier nombre 123 456, tu as fait la liste pour tout nombre premier inférieur à 61 728.
Deuxième nombre 12345, pas besoin de calculer un nouveau crible.
Troisième nombre 234567, tu n'as besoin de calculer un crible que de 61 729 à 117 284
d'abord pour présenter correctement un code, voir ce petit tuto https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code
Ensuite, la recherche de nombre premier est toujours très longue.
On appelle ça un crible, tu en trouveras plusieurs sur le net, notamment chez "nous" en C
https://codes-sources.commentcamarche.net/source/s/crible/last William VOIROL s'en est fait une spécialité.
Si on en croit ses commentaires, le cible segmenté de Kim Wallisch serait un des (le?) plus rapide. Il a même écrit une page avec les résultats de ses tests.
http://www.william-voirol.ch/Prog/Maths/Prime/
Ensuite tu cherches le plus grand facteur premier, mais tu commences par 2, c'est le plus petit... et surtout, tu testes tous les nombres.
Moi je ferai une liste (un crible) de tous les nombres premiers entre 2 et nb/2 et je ne testerai la division que de ces nombres. Ainsi le test de primalité n'est fait qu'une seule fois, et le nombre de divisions est très fortement limités.
Après d'instinct, je commencerai par tester la division avec le nombre le plus grand, puis le plus grand restant etc... mais sans garantie d'optimiser la vitesse d'exécution. En effet, il y a des nombres très grands dont le plus grand facteur premier est très petit.
Par exemple pour 2^1000, c'est 2.
Mais l'avantage de commencer par le plus grand c'est que le premier facteur trouvé est aussi le plus grand. Donc on ne continue pas à chercher. Empiriquement je pense qu'il y a plus de cas où c'est un avantage qu'un inconvenient.
Enfin, si tu dois chercher le plus grand facteur de plusieurs nombres, garde la liste de nombres premier et complète là au fur et à mesure si besoin.
Par exemple premier nombre 123 456, tu as fait la liste pour tout nombre premier inférieur à 61 728.
Deuxième nombre 12345, pas besoin de calculer un nouveau crible.
Troisième nombre 234567, tu n'as besoin de calculer un crible que de 61 729 à 117 284
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
1 568
9 févr. 2020 à 10:38
9 févr. 2020 à 10:38
l'un et l'autre, vous ne tenez pas compte qu'il s'agit d'une recherche de facteurs. que peut-on faire dès qu'on a trouvé un facteur, avant de chercher les autres facteurs? sans négliger qu'un facteur peut diviser plusieurs fois un nombre!
skywalker27
>
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
9 févr. 2020 à 12:17
9 févr. 2020 à 12:17
merci pour cette remarque, il faut donc que le nb soit remplacé par nb/i.
Merci whismeril.
Tu proposes l'exact inverse de ce que j'avais imaginé au départ, qui était de trouver d'abord les facteurs puis de voir lesquels sont premiers pour ne garder que le plus grand.
Si je comprends bien, ta solution s'appuie sur une liste de nombre premiers établie au préalable, sur laquelle on vient prendre les facteurs en commencant par le haut, pour venir trouver le facteur le plus grand.
Je vais regarder pour les différents cribles.
Tu proposes l'exact inverse de ce que j'avais imaginé au départ, qui était de trouver d'abord les facteurs puis de voir lesquels sont premiers pour ne garder que le plus grand.
Si je comprends bien, ta solution s'appuie sur une liste de nombre premiers établie au préalable, sur laquelle on vient prendre les facteurs en commencant par le haut, pour venir trouver le facteur le plus grand.
Je vais regarder pour les différents cribles.
Utilisateur anonyme
9 févr. 2020 à 11:21
9 févr. 2020 à 11:21
Salut,
c’est exact, je pensais lui en parler ensuite.
De fait c’est contradictoire avec l’idée de commencer par le plus grand. Donc je m’étais dit que je pouvais lui proposer cette option, puis celle que tu suggères et qu’ensuite il teste sur un grand nombre de cas ce qui est le plus rapide.
c’est exact, je pensais lui en parler ensuite.
De fait c’est contradictoire avec l’idée de commencer par le plus grand. Donc je m’étais dit que je pouvais lui proposer cette option, puis celle que tu suggères et qu’ensuite il teste sur un grand nombre de cas ce qui est le plus rapide.
Utilisateur anonyme
9 févr. 2020 à 12:42
9 févr. 2020 à 12:42
En cumulant la remarque de yg_be et ma proposition.
Au fur et à mesure que tu construis le crible, tu cherches les facteurs. Et tu réduis la plage de recherche.
Par exemple pour 102.
Il est divisible par 2 -> 51, donc maintenant le plus grand diviseur premier est forcément inférieur à 25, sauf si 51 est premier.
51 n'est pas divisible par 2
51 est divisible par 3 -> 17, donc maintenant le plus grand diviseur premier est forcément inférieur à 8 sauf si 17 est premier
etc....
Rien n'empêche de constituer une liste de nombre premier si ton programme doit tester plusieurs nombre à la suite et la compléter quand c'est nécessaire.
Au fur et à mesure que tu construis le crible, tu cherches les facteurs. Et tu réduis la plage de recherche.
Par exemple pour 102.
Il est divisible par 2 -> 51, donc maintenant le plus grand diviseur premier est forcément inférieur à 25, sauf si 51 est premier.
51 n'est pas divisible par 2
51 est divisible par 3 -> 17, donc maintenant le plus grand diviseur premier est forcément inférieur à 8 sauf si 17 est premier
etc....
Rien n'empêche de constituer une liste de nombre premier si ton programme doit tester plusieurs nombre à la suite et la compléter quand c'est nécessaire.
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
1 568
Modifié le 9 févr. 2020 à 12:55
Modifié le 9 févr. 2020 à 12:55
si on n'a pas trouvé de diviseur inférieur à la racine carrée, inutile de continuer à chercher; le plus grand diviseur est le nombre restant (17 dans l'exemple, puisqu'il n'y a plus de nombre premier plus grand que 3 et plus petit que la racine carrée de 17).
si on a une liste de nombres premiers, il ne faut chercher de diviseur que dans cette liste.
si on a une liste de nombres premiers, il ne faut chercher de diviseur que dans cette liste.
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
1 568
>
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
9 févr. 2020 à 20:51
9 févr. 2020 à 20:51
sans constituer de liste, en faisant simplement comme on ferait à la main, ceci est déjà assez rapide:
import math
def pgfp(nb):
candidatfacteur=2
plafondcandidatfacteur = math.floor(math.sqrt(nb))
while candidatfacteur <= plafondcandidatfacteur :
if nb%candidatfacteur==0:
nb=int(nb/candidatfacteur)
plafondcandidatfacteur = math.floor(math.sqrt(nb))
else:
candidatfacteur += 1 # on pourrait optimiser en cherchant le prochain nombre premier, si on a une liste
return nb
def pg_facteur_premier(nbr):
print ("___",nbr,pgfp(nbr))
pg_facteur_premier(2*3*7*16*7*5)
pg_facteur_premier(1)
pg_facteur_premier(2)
pg_facteur_premier(17)
pg_facteur_premier(2000)
pg_facteur_premier(999)
pg_facteur_premier(806515533049393)
pg_facteur_premier(806515533049393+1)
pg_facteur_premier(806515533049393-1)
pg_facteur_premier(704598937319-1)
pg_facteur_premier(704598937319)
pg_facteur_premier(704598937319+1)
pg_facteur_premier(999000016669-1)
pg_facteur_premier(999000016669)
pg_facteur_premier(999000016669+1)
pg_facteur_premier(2705189*54018521*86020717)
pg_facteur_premier(806515533049393*999000016669/8362842642432)
pg_facteur_premier(8362842642432)
pg_facteur_premier(453713251)
trifou
>
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
10 févr. 2020 à 10:33
10 févr. 2020 à 10:33
Bonjour,
Une bonne amélioration à faire serait d'ignorer les nombres pairs, donc partir du 3 et aller de 2 en 2.
C'est fait à la rache, sans doute quelques trucs à optimiser ^^
Une bonne amélioration à faire serait d'ignorer les nombres pairs, donc partir du 3 et aller de 2 en 2.
from math import sqrt
def facteur(n):
if not n % 2:
return 2
for i in range(3, int(sqrt(n)) + 1, 2):
if not n % i:
return i
return 0
def pg_facteur_premier(nb):
premiers = []
if nb == 1:
premiers.append(nb)
while nb > 1:
fn = facteur(nb)
try:
nb //= fn
except ZeroDivisionError:
premiers.append(nb)
break
premiers.append(fn)
return premiers[-1]
C'est fait à la rache, sans doute quelques trucs à optimiser ^^
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
1 568
>
trifou
10 févr. 2020 à 11:04
10 févr. 2020 à 11:04
une fois qu'on a identifié un facteur, il est inutile, par la suite, de vérifier si les nombres inférieurs à ce facteur sont des facteurs. d'où ma suggestion en une boucle.
ou bien passer un second paramètre à la fonction facteur: le plus petit facteur à tester (2 au départ, ensuite fn)
ou bien passer un second paramètre à la fonction facteur: le plus petit facteur à tester (2 au départ, ensuite fn)
trifou
>
yg_be
Messages postés
23473
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
18 février 2025
10 févr. 2020 à 13:10
10 févr. 2020 à 13:10
Testé, mais ça ne fait pas vraiment gagner grand-chose, quelques pouillèmes de secondes.
Du moins si dont tu parles est de faire quelque chose comme
Du moins si dont tu parles est de faire quelque chose comme
from math import sqrt
def facteur(n, start):
if not n % 2:
return 2
if not start % 2: # 0 ou 2
start = 3
for i in range(start, int(sqrt(n)) + 1, 2):
if not n % i:
return i
return 0
def pg_facteur_premier(nb):
premiers = []
if nb == 1:
premiers.append(nb)
fn = 0
while nb > 1:
fn = facteur(nb, fn)
try:
nb //= fn
except ZeroDivisionError:
premiers.append(nb)
break
premiers.append(fn)
return premiers[-1]