Sujet Précédent Sujet Suivant

Algo optimisé - plus grand facteur premier

Fermé
skywalker27 - Modifié le 9 févr. 2020 à 09:39
 trifou - 10 févr. 2020 à 13:10
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

Réponse 1 / 4
yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024 1 476
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à.
1
Réponse 2 / 4
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 931
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




0
yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024 1 476
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!
0
skywalker27 > yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024
9 févr. 2020 à 12:17
merci pour cette remarque, il faut donc que le nb soit remplacé par nb/i.
0
skywalker27
9 févr. 2020 à 12:22
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.
0
Réponse 3 / 4
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 931
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.
0
Réponse 4 / 4
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 931
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.

0
yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024 1 476
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.
0
yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024 1 476 > yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024
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)
0
trifou > yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024
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. 

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 ^^
0
yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024 1 476 > trifou
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)
0
trifou > yg_be Messages postés 22724 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 25 avril 2024
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 

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]
0

Discussions similaires

Snapchat locked : mon compte snapchat est bloqué
amelie-2 -
Beratilhan -

51 réponses
Comment trouver un numéro à partir du nom et prénom
papillon -
guyguy -

10 réponses
Comment retrouver le presse papier sur iPhone ?
Slilluu -
Ascaris -

6 réponses
Trouver propriétaire d'un numéro de téléphone gratuitement
assiakellil -
Eli -

5 réponses
Trouver un nom avec une adresse
lakshmi66 -
Nath01 -

11 réponses