Programmation fonctionnelle dans Python Project Euler 3

Problem 3 - Project Euler

"Facteur premier maximum"

Les facteurs premiers de 13195 sont 5, 7, 13, 29.

Trouvez le plus grand des facteurs premiers de 600851475143.

Solution

Commencez par 2 et recherchez les facteurs dans l'ordre croissant, puis répétez récursivement le processus de division par la valeur chaque fois qu'un facteur est trouvé pour trouver le plus grand facteur premier. Nous utilisons une technique fonctionnelle pour trouver le premier élément qui correspond à la condition selon laquelle l'entier reçu en argument est divisible.

Fonction pour trouver le premier élément

Je pense qu'il est normal que les langages fonctionnels aient une fonction qui trouve le premier élément qui correspond à une condition donnée.

Il n'y a pas de fonction similaire en Python, vous devez donc combiner des fonctions existantes. Vous pouvez obtenir le premier élément en générant un itérateur qui ne renvoie que ceux qui remplissent les conditions avec la fonction de filtre et en passant cet itérateur à la fonction suivante.

def find(condition, iterable):
    return next(filter(condition, iterable), None)

Dans la définition de fonction ci-dessus, condition est la fonction qui détermine la condition, iterable est un objet tel qu'une liste, et le dernier None est la valeur renvoyée lorsqu'il n'y a pas d'élément.

Exemple de réponse

Python_3.x

# -*- coding: UTF-8 -*-
from math import sqrt


def find(pred, iterable):
    '''Trouvez le premier élément qui correspond aux critères. Renvoie None s'il n'y a pas d'éléments correspondants.'''
    return next(filter(pred, iterable), None)


def getMaxPrimeFactor(n):
    '''Trouvez le facteur premier maximum.'''
    #️ Trouvez le plus petit facteur compris entre 2 et √n.
    limit = int(sqrt(n))
    smallestFactor = find(lambda i: n % i == 0, range(2, limit + 1))
    if smallestFactor is None:
        #Renvoie n si aucun facteur n'est trouvé.
        return n
    else:
        #️ Si un facteur est trouvé, appelez récursivement en divisant n par le facteur.
        return getMaxPrimeFactor(n // smallestFactor)


answer = getMaxPrimeFactor(600851475143)
print(answer)

Si vous l'exécutez avec Python 2.x, une erreur se produira, vous pouvez donc l'exécuter correctement en remplaçant la fonction de filtre par la fonction ifilter du module itertools.

Python_2.x

# -*- coding: UTF-8 -*-
from math import sqrt
from itertools import ifilter


def find(pred, iterable):
    '''Trouvez le premier élément qui correspond aux critères. Renvoie None s'il n'y a pas d'éléments correspondants.'''
    return next(ifilter(pred, iterable), None)


def getMaxPrimeFactor(n):
    '''Trouvez le facteur premier maximum.'''
    #️ Trouvez le plus petit facteur compris entre 2 et √n.
    limit = int(sqrt(n))
    smallestFactor = find(lambda i: n % i == 0, range(2, limit + 1))
    if smallestFactor is None:
        #Renvoie n si aucun facteur n'est trouvé.
        return n
    else:
        #️ Si un facteur est trouvé, appelez récursivement en divisant n par le facteur.
        return getMaxPrimeFactor(n // smallestFactor)


answer = getMaxPrimeFactor(600851475143)
print(answer)