/
xddxdd
/
Python
Обзор
Документация
Войти
/
xddxdd
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
project_euler/problem_072/sol2.py
45 строк
1 KB
fpringle
Add solution for Project Euler problem 72 (#3122)
16 окт 2020, 12:42
Не верифицирован
16 окт 2020, 12:42
d8f5b31
Код
Авторство
О чём код?
""" Project Euler Problem 72: https://projecteuler.net/problem=72 Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction. If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get: 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 It can be seen that there are 21 elements in this set. How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000? """ def solution(limit: int = 1000000) -> int: """ Return the number of reduced proper fractions with denominator less than limit. >>> solution(8) 21 >>> solution(1000) 304191 """ primes = set(range(3, limit, 2)) primes.add(2) for p in range(3, limit, 2): if p not in primes: continue primes.difference_update(set(range(p * p, limit, p))) phi = [float(n) for n in range(limit + 1)] for p in primes: for n in range(p, limit + 1, p): phi[n] *= 1 - 1 / p return int(sum(phi[2:])) if __name__ == "__main__": print(f"{solution() = }")