Functional programming in Python Project Euler 3

Problem 3 - Project Euler

"Maximum prime factor"

The prime factors of 13195 are 5, 7, 13, 29.

Find the largest of the prime factors of 600851475143.

solution

Start with 2 and search for factors in ascending order, then recursively repeat the process of dividing by the value each time a factor is found to find the largest prime factor. We use a functional technique to find the first element that matches the condition that the integer received as an argument is divisible.

Function to find the first element

I think it's normal for functional languages to have a function that finds the first element that matches a given condition.

There is no similar function in Python, so you need to combine existing functions. You can get the first element by generating an iterator that returns only those that meet the conditions with the filter function and passing that iterator to the next function.

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

In the function definition above, condition is the function that determines the condition, iterable is an object such as a list, and the last None is the value returned when there is no element.

Answer example

Python_3.x

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


def find(pred, iterable):
    '''Find the first element that matches the criteria. Returns None if there are no matching elements.'''
    return next(filter(pred, iterable), None)


def getMaxPrimeFactor(n):
    '''Find the maximum prime factor.'''
    #️ Find the smallest factor in the range 2 to √n.
    limit = int(sqrt(n))
    smallestFactor = find(lambda i: n % i == 0, range(2, limit + 1))
    if smallestFactor is None:
        #Returns n if no factor is found.
        return n
    else:
        #️ If a factor is found, call recursively by dividing n by the factor.
        return getMaxPrimeFactor(n // smallestFactor)


answer = getMaxPrimeFactor(600851475143)
print(answer)

If you execute it with Python 2.x, an error will occur, so you can execute it correctly by replacing the filter function with the ifilter function of the itertools module.

Python_2.x

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


def find(pred, iterable):
    '''Find the first element that matches the criteria. Returns None if there are no matching elements.'''
    return next(ifilter(pred, iterable), None)


def getMaxPrimeFactor(n):
    '''Find the maximum prime factor.'''
    #️ Find the smallest factor in the range 2 to √n.
    limit = int(sqrt(n))
    smallestFactor = find(lambda i: n % i == 0, range(2, limit + 1))
    if smallestFactor is None:
        #Returns n if no factor is found.
        return n
    else:
        #️ If a factor is found, call recursively by dividing n by the factor.
        return getMaxPrimeFactor(n // smallestFactor)


answer = getMaxPrimeFactor(600851475143)
print(answer)