오일러 프로젝트 29 번은 밑과 지수의 조합들에게서 중복을 제외한 값들을 골라내는 작업이다. 일견 단순해 보이는데, 큰 수를 지원하지 않는다면 조금 돌아가야 하는 곤란함이 있다.
2 ≤ a ≤ 5 이고 2 ≤ b ≤ 5인 두 정수 a, b로 만들 수 있는 a**b의 모든 조합을 구하면 다음과 같습니다.
2**2=4, 2**3=8, 2**4=16, 2**5=32 3**2=9, 3**3=27, 3**4=81, 3**5=243 4**2=16, 4**3=64, 4**4=256, 4**5=1024 5**2=25, 5**3=125, 5**4=625, 5**5=3125
여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다.
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
그러면, 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 a**b는 중복을 제외하면 모두 몇 개입니까?
http://euler.synap.co.kr/prob_detail.php?id=29
접근
파이썬에서는 2에서 100까지 2단 루프를 돌면서 
set())에 담으면 간단하게 계산할 수 있다. 100^100은 엄청 큰 수이지만, 여기서는 별 문제가 되지 않는다.
def e029():
a = set()
for x in range(2, 101):
for y in range(2, 101):
a.add(x**y)
print(len(a))
%time e029()
#Wall time: 15 ms큰수를 지원하지 않는 경우
Swift와 같이 큰수를 지원하지 않는 경우가 문제이다. BigNumber 에 Equtable, Hashable 을 구현해서 파이썬과 똑같이 Set<BigNumber> 를 이용하는 방법도 있겠지만, 여기서는 좀 다른 식으로 접근해보자. 지수로 표현된 값을 튜플로 표현해보자. 예를 들어 
(8, 6) 으로 표시하는 것이다. 그런데 이 값은 사실 (2^3, 6)이고 이는 지수법칙 
(2,18) 과 같아진다. a의 범위가 2…100 이고 100은 2^7보다 작으므로 2..<a 범위에서 2…7 제곱을 수행하여 매칭되는 케이스가 있으면 변환하면 된다.
참고로 Swift에서 (Int, Int) 타입은 Hashable 이 아니며 따라서 Set에 들어갈 수 없다. 그래서 부득이 하게 “a^b”의 문자열 꼴로 변경해서 저장한다. 최종 구현은 다음과 같다.
import Foundation
func transform(_ x: (Int, Int)) -> (Int, Int) {
let (a, b) = x
for i in 2..<a {
for j in 2..<7 {
let k = Int(pow(Double(i), Double(j)))
if k == a { return (i, b * j) }
if k > a { break }
}
}
}
main: do {
var s = Set<String>()
for a in 2...100 {
for b in 2...100 {
let c = transform(a, b)
s.insert("\(c.0)^\(c.1)")
}
}
print(s.count)
}