LUCAS WILLEMS
Un étudiant de 27 ans passionné par les maths et la programmation
Un étudiant de 27 ans passionné par les maths et la programmation
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 ?
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 :
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.
La réponse à ce problème est 6857.
Voici les recherches relatives à cette page :
Qu'en pensez-vous ? Donnez moi votre avis (positif ou négatif) pour que je puisse l'améliorer.