Lucas Willems

LUCAS WILLEMS

Un étudiant de 27 ans passionné par les maths et la programmation

English

Project Euler 3 : solution Python

Article

Voici un résumé de l'énoncé du problème 3 "Largest prime factor" du Project Euler (traduction complète en français ici) :

What is the largest prime factor of the number 600851475143 ?

Compréhension du problème

Reformulons notre problème : il s'agit de trouver le plus grand facteur de 600851475143 qui soit premier. Grâce à cette reformulation, nous pouvons distinguer les différentes étapes de la résolution de notre problème :

  1. Trouver tous les facteurs de 600851475143
  2. Les trier dans l'ordre décroissant pour avoir les plus grands facteurs en premier
  3. Tester les facteurs dans l'ordre pour savoir s'ils sont premiers. Le premier facteur qui est premier correspond à notre résultat.

Le programme

Voici une des solutions possibles, en Python, pour résoudre ce problème :

def is_prime(nb):
    if nb == 1:
        return False
    if nb == 2:
        return True
    elif nb%2 == 0:
        return False
    for i in range(3, int(nb**0.5)+1, 2):
        if nb%i == 0:
            return False
    return True
def divisors(nb, extremum = False): divisors = [] inf = 1 if extremum else 2 for i in range(inf, int(nb**0.5)+1): q, r = divmod(nb, i) if r == 0: if q >= i: divisors.append(i) if q > i: divisors.append(nb//i) return divisors
#Tri des diviseurs dans l'ordre décroissant divs = divisors(600851475143) divs.sort(reverse=True) #Lit un par un les diviseurs et teste s'ils sont premiers. #Si c'est le cas, on affiche le diviseur et sort de la boucle. for i in divs: if is_prime(i): print(i) break

Comme les fonctions \(\text{is_prime}\) et \(\text{divisors}\) ne sont pas des fonctions spécifiques à ce problème, les explications les concernant se trouvent dans cet article pour éviter de les réécrire sur d'autres problèmes.

Le résultat

La réponse à ce problème est 6857.

Recherche

Voici les recherches relatives à cette page :

Commentaires

Qu'en pensez-vous ? Donnez moi votre avis (positif ou négatif) pour que je puisse l'améliorer.