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.

language Function name
F# find
Scala find
C# (LINQ) First
Java 8 -

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)

Recommended Posts

Functional programming in Python Project Euler 1
Functional programming in Python Project Euler 3
Functional programming in Python Project Euler 2
[Note] Project Euler in Python (Problem 1-22)
Project Euler # 5 "Minimum Multiples" in Python
Programming in python
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
Try a functional programming pipe in Python
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Python programming in Excel
What is "functional programming" and "object-oriented" in Python?
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 12 "High Divisibility Triangular Number" in Python
Project Euler # 13 "Sum of Large Numbers" in Python
Project Euler # 6 "Difference in sum of squares" in Python
Get in touch with functional programming in JavaScript or Python 3
Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 31
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Create Python project documentation in Sphinx
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 11 "Maximum product in grid"
Project Euler 13
Project Euler 30