오일러 프로젝트 87번

보다 영리하게 푸는 방법은 여전히 모르겠고, 현재로서는 brute-force로 푸는 것이 최선인 것 같다. 5천만이라는 한계값이 정해져 있으므로 범위 내에서 에라토스테네스의 체를 사용해서 소수 세트를 미리 만들어 놓고 삼중 루프를 돌면서 범위를 벗어나지 않는 값들을 집합에 더하는 식으로 계산한다. 이 때 작은 값부터 더해나가면서 한계치를 초과하는 부분을 쓸데없이 계산하지 않도록만 해준다.

필요한 가장 큰 소수는 대략 5천만의 제곱근 수준인 것 같다. (정확히는 5천만 – 8 – 16 의 제곱근) 소수체만 잘 만들 수 있다면 파이썬으로도 1초 이내에 계산 가능하다. (600~700 ms 수준)

def sieve(n: int) -> list[int]:
    cs = [1] * (n + 1)
    cs[:2] = [0, 0]
    for i in range(2, int(n ** 0.5 + 1.5)):
        if cs[i]:
            cs[i + i :: i] = [0] * ((n - i) // i)
    return [x for x, c in enumerate(cs) if c]


def main(l=5000_0000):
    ps = sieve(int((l - 8 - 16) ** 0.5 + 0.5))
    res = set()
    for a in (p ** 2 for p in ps):
        for b in (p ** 3 for p in ps):
            if a + b > l:
                break
            for c in (p ** 4 for p in ps):
                x = a + b + c
                if x > l:
                    break
                res.add(x)
    return len(res)


print(main())