Funktionale Programmierung in Python Project Euler 3

Problem 3 - Project Euler

"Maximaler Primfaktor"

Die Primfaktoren von 13195 sind 5, 7, 13, 29.

Finden Sie den größten der Primfaktoren von 600851475143.

Lösung

Beginnen Sie mit 2 und suchen Sie nach Faktoren in aufsteigender Reihenfolge. Wiederholen Sie dann rekursiv den Vorgang des Dividierens durch den Wert jedes Mal, wenn ein Faktor gefunden wird, um den größten Primfaktor zu finden. Wir verwenden eine funktionale Technik, um das erste Element zu finden, das der Bedingung entspricht, dass die als Argument empfangene Ganzzahl teilbar ist.

Funktion zum Finden des ersten Elements

Ich denke, es ist normal, dass funktionale Sprachen eine Funktion haben, die das erste Element findet, das einer bestimmten Bedingung entspricht.

In Python gibt es keine ähnliche Funktion, daher müssen Sie vorhandene Funktionen kombinieren. Sie können das erste Element erhalten, indem Sie einen Iterator generieren, der nur diejenigen zurückgibt, die die Bedingungen mit der Filterfunktion erfüllen, und diesen Iterator an die nächste Funktion übergeben.

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

In der obigen Funktionsdefinition ist Bedingung die Funktion, die die Bedingung bestimmt, iterierbar ist ein Objekt wie eine Liste, und die letzte Keine ist der Wert, der zurückgegeben wird, wenn kein Element vorhanden ist.

Antwortbeispiel

Python_3.x

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


def find(pred, iterable):
    '''Suchen Sie das erste Element, das den Kriterien entspricht. Gibt None zurück, wenn keine übereinstimmenden Elemente vorhanden sind.'''
    return next(filter(pred, iterable), None)


def getMaxPrimeFactor(n):
    '''Finden Sie den maximalen Primfaktor.'''
    #️ Finden Sie den kleinsten Faktor im Bereich von 2 bis √n.
    limit = int(sqrt(n))
    smallestFactor = find(lambda i: n % i == 0, range(2, limit + 1))
    if smallestFactor is None:
        #Gibt n zurück, wenn kein Faktor gefunden wird.
        return n
    else:
        #️ Wenn ein Faktor gefunden wird, rufen Sie rekursiv auf, indem Sie n durch den Faktor dividieren.
        return getMaxPrimeFactor(n // smallestFactor)


answer = getMaxPrimeFactor(600851475143)
print(answer)

Wenn Sie es mit Python 2.x ausführen, tritt ein Fehler auf, sodass Sie es korrekt ausführen können, indem Sie die Filterfunktion durch die ifilter-Funktion des itertools-Moduls ersetzen.

Python_2.x

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


def find(pred, iterable):
    '''Suchen Sie das erste Element, das den Kriterien entspricht. Gibt None zurück, wenn keine übereinstimmenden Elemente vorhanden sind.'''
    return next(ifilter(pred, iterable), None)


def getMaxPrimeFactor(n):
    '''Finden Sie den maximalen Primfaktor.'''
    #️ Finden Sie den kleinsten Faktor im Bereich von 2 bis √n.
    limit = int(sqrt(n))
    smallestFactor = find(lambda i: n % i == 0, range(2, limit + 1))
    if smallestFactor is None:
        #Gibt n zurück, wenn kein Faktor gefunden wird.
        return n
    else:
        #️ Wenn ein Faktor gefunden wird, rufen Sie rekursiv auf, indem Sie n durch den Faktor dividieren.
        return getMaxPrimeFactor(n // smallestFactor)


answer = getMaxPrimeFactor(600851475143)
print(answer)