Algo optimisé - plus grand facteur premier

Signaler
-
 trifou -
Bonjour,

Je cherche à déterminer le plus grand facteur premier d'un nombre.

Je dois donc trouver les facteurs premiers d'un nombre, à l'aide d'un test de primalité, puis je retourne le plus grand dans la liste.

Mon programme fonctionne, mais il est extrêment lent pour les grands nombres.

Comment puis-je optimiser mon programme ?

Voici mes deux fonctions:

----------------------------------------------------------------------------------------------------------------------------------------
def primalite(n):

___for i in range(2,(n//2)+1):
_____if n%i==0:
________return 0
___return 1

#le test de primalité retourne 1 pour un nb premier, 0 pour un nb non-premier
#le test ne marche pas pour n=1; mais c'est pas grave.

-----------------------------------------------------------------------------------------------------------------------------------------

def pg_facteur_premier(nb):

___F=[ ]
___for i in range(2,(nb//2)+1):
_____if nb%i==0 and primalite(i)==1: #si le nombre i est facteur de nb ET premier
________F.append(i) #alors i est ajouté à la liste, remplie dans l'ordre croissant

___if F==[ ]:
_____return nb #si le nombre n'a pas de facteur premier, il est son plus grand facteur premier

___else:
_____return F[len(F)-1] #sinon, on prend le plus grand nombre dans la liste de facteur premiers

-----------------------------------------------------------------------------------------------------------------------------------------

pg_facteur_premier(67) --> 67
pg_facteur_premier(123) --> 41
pg_facteur_premier(6520) --> 163
pg_facteur_premier(806515533049393) --> le programme tourne, tourne...

Merci d'avance pour vos contributions.





Configuration: Windows / Chrome 80.0.3987.87

4 réponses

Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020
708
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à.
Messages postés
14907
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
24 octobre 2020
596
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




Quand j'étais petit, la mer Morte n'était que malade.
George Burns
Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020
708
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!
>
Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020

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.
Messages postés
14907
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
24 octobre 2020
596
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.
Messages postés
14907
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
24 octobre 2020
596
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.

Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020
708
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.
Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020
708 >
Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020

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)
>
Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020

Bonjour,

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 ^^
Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020
708 > trifou
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)
>
Messages postés
12752
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
24 octobre 2020

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

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]