project euler problem 72 https projecteuler netproblem72 consider the fraction nd where n and d are positive integers if nd and hcfn d1 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 18 17 16 15 14 27 13 38 25 37 12 47 35 58 23 57 34 45 56 67 78 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 return the number of reduced proper fractions with denominator less than limit solution8 21 solution1000 304191 return the number of reduced proper fractions with denominator less than limit solution 8 21 solution 1000 304191
def solution(limit: int = 1000000) -> int:
    
    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() = }")