Bonjour,

Je m'exerce sur le site "Project Euler" et j'ai un petit problème dans l'exo 3.J'ai fait l'algo suivant pour trouver le plus grand facteur premier d'un nombre.

#The prime factors of 13195 are 5, 7, 13 and 29.

#What is the largest prime factor of the number 600851475143 ?


def IsPrime(n):
    if (n == 1):
        return False
    elif (n == 0):
        return False
    i = n - 1
    while (i > 1):
        if(n % i == 0):
            return False
        i -= 1
    return True

if __name__ == "__main__":
    n = 13195  
    i = n - 1
    while i > 1:
        if n % i == 0:
            if IsPrime(i) :
                break
        i -=1

    print(i)

Pouvez vous m'expliquer pourquoi ce code est si peu performant. Comment pourrait on l'optimiser pour répondre à la question demandée (le résultat pour n = 60085147514) ?

Merci

-
Edité par zaki95 4 avril 2020 à 21:27:27

Ton algorithme est ingérable du point de vue de la complexité algorithmique. Tu cherches en fait tous les facteurs (premiers ou pas) en commençant par les plus grands et pour chacun d'entre eux tu testes s'il est premier et sinon tu cherches en dessous. Mais rien que chercher le plus grand facteur (même pas premier) va être extrêmement long dans ton exemple n=600851475143.

En utilisant SageMath (sur cocalc par exemple), tu vas voir que son plus grand facteur est dmax=8462696833. C'est grand mais avec ta méthode, tu vas devoir parcourir tous les entiers entre n et ce plus grand diviseur, et le fossé est énorme, il est de n-dmax=592388778310, quasiment la taille de ton nombre n, donc ingérable. 

Donc l'astuce minimale pour faire cet exo (et beaucoup d'autres) c'est de savoir que si un entier n'est pas premier, il a un diviseur <= à sa racine carrée, ce qui diminue énormément la recherche, dans le cas de ton nombre n ci-dessus, elle vaut  775146, moins de 1 million, donc c'est facilement parcourable avec un boucle for. Si tu parcours sans trouver de diviseur, c'est que le nombre est premier. Donc il suffit que tu refasses ce que tu as fait mais en commençant juste avant la racine carrée.

-
Edité par PascalOrtiz 4 avril 2020 à 23:29:51

Merci pour ta réponse, j'ai testé ce programme en suivant tes conseils, je ne sais pas s'il correspond à ce que tu avais en tête mais effectivement, il n'y a pas photo. En une seconde j'ai le résultat :

#The prime factors of 13195 are 5, 7, 13 and 29.

#What is the largest prime factor of the number 600851475143 ?


def IsPrime(n):
    if (n == 1):
        return False
    elif (n == 0):
        return False
    elif(n==2):
        return True
    elif (n%2 == 0):
        return False
    else :
        i = int(n**0.5)
        while (i > 1) :
            if n%i == 0:
                return False
            i -= 1
        return True

if __name__ == "__main__":

    n = 600851475143  
    i = int(n**0.5)
    while i > 1:
        if n % i == 0:
            if IsPrime(i) :
                break
        i-= 1
    print(i)

Tu vois bien qu'il ne trouve temps, dans un temps raisonnable (moins de quelques siècles  ).

Une idée : tu pars des facteurs premiers les plus petits, tu divises le nombre à traiter n par la meilleure puissance du nombre premier courant et ton nombre va diminuer, et recommence avec le nombre diviseur suivant.

Pour 11**42, tu testes 2, 3, etc jusqu'à 10 (aucune division ne marche) tu arrives à 11, ça divise et tu réitères autant de fois que possible (42 fois).

Essaye 547636993415439302363626340039649032878945411509663899 qui lui est un peu moins simple.