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.