어떤 소수의 제곱, 세제곱, 네제곱의 합으로 표현할 수 있는 수를 찾는 문제.
소수의 제곱 + 소수의 3제곱 + 소수의 4제곱)으로 나타낼 수 있는 가장 작은 수는 28입니다.
28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24
50 미만에 이런 수는 모두 네 개 있습니다. 5천만 미만에 이렇게 나타낼 수 있는 수는 모두 몇 개나 됩니까?
보다 영리하게 푸는 방법은 여전히 모르겠고, 현재로서는 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())