The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:
28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24
How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?
소수의 제곱, 세제곱, 네제곱의 합계로 구할 수 있는 가장 작은 수는 28이다. 실제로, 소수의 제곱, 세제곱, 네제곱을 합하여 구할 수 있는 50이하의 수는 다음과 같이 4가지가 있다:
28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24
소수의 제곱, 세제곱, 네제곱의 합으로 구할 수 있는 5천만 이하의 숫자는 몇가지인가?
--------------------------------------------------------------------------
문제 난이도는 20%로 높게 책정되어 있지만, 그동안 많이 다뤄왔던 소수의 연장선에 있고 파이썬이 큰 숫자를 쉽게 다룰 수 있게 지원하기 때문에 그렇게 어렵지 않게 해결할 수 있었다. 문제 난이도를 생각하면 좀 더 빠르게 해결가능한 방법이 있을 것 같았지만, 문제에서 요구하는 정석대로 접근해서 해결했다.
5천만 이하의 소수의 제곱, 세제곱, 네제곱을 구하고, 이것을 반복문을 통해 서로 더해나가면 어렵지 않게 구할 수 있다.
처음에, 문제에 있는 prime을 간과한 덕분에 모든 자연수의 제곱, 세제곱, 네제곱을 구하고, 반복문을 통해 더한 것을 모두 나열하니 1.47억개의 리스트가 나왔고, 여기에서 중복을 제거하려 하니 몇시간이 걸려도 답이 나오지 않는 상황이 발생했다.
문제를 다시 읽어보니 소수를 대상으로 하는 것이어서 제곱, 세제곱, 네제곱이 훨씬 적게 되고, 마지막에 중복을 제거하지 않고 집합 자료형을 이용하여 중복을 제거하면서 합을 구했더니 훨씬 간단한 로직으로 구할 수 있었다.