프로젝트 오일러 029
2와 100사이의 수들을 밑과 지수로 했을 때, 중복을 제외한 값의 개수
파이썬과 같이 큰 수의 연산을 지원하는 언어에서는 사실 너무 쉬운 문제입니다. 이중 루프를 지능형 리스트로 만들고, 중복을 제거하기 위해 set를 이용하면 됩니다.
print(len(set(x**y for x in range(2, 101) for y in range(2,101))))지수법칙
큰 수의 연산을 사용하지 않더라도 이 문제는 간단합니다. 편의상 라는 표기를 튜플을 사용해서 (x, y)라고 표기하기로 임의로 정하겠습니다. 은 (8, 7)로 표기하는 식입니다. 그런데 8은 2의 세제곱이므로 지수법칙에 의해 (8, 7) = (2, 21)이 됩니다. 이런식으로 밑이 특정 수의 제곱수인지를 확인하여 작은 밑을 사용하는 표기로 변경하면 거듭제곱 계산을 수행하지 않아도 중복인지 알아낼 수 있습니다. 그러면 특정한 숫자쌍을 더 작은 밑을 사용하는 다른 표기로 치환할 수 있는지 살펴보면 됩니다.
문제에서 밑이 될 수 있는 수는 1100사이의 자연수입니다. 2의 거듭제곱을 살펴보면 2의 8제곱은 128로 100보다 큽니다. 따라서 100이하의 모든 수는 29사이의 7제곱보다 작거나, 제곱수가 아닌 수입니다. 이 성질을 이용해 보겠습니다. 참고로 파이썬의 math.log에서 밑은 두 번째 인자로 전달되어야 하는 점에 유의해야 합니다.
from math import log
def lower_base(a: int, b: int) -> tuple[int, int]:
"""a의 b거듭제곱을 더 작은 밑을 가진 지수 표현으로 변환"""
for i in range(2, a):
j = int(log(a, i))
if i ** j == a:
return (i, b * j)
return (a, b)
print(len(set(lower_base(x, y) for x in range(2, 101) for y in range(2, 101))))효율적인 큰 수의 지수 계산 방법
앞서 작성한 큰 수의 곱셈 사용하여 직접 계산하는 방법을 사용하여 이 문제를 풀 수도 있습니다. 이 때 100제곱을 계산하기 위해서 루프로 100번 곱하는 것보다는 좀 더 효율적인 방법이 있습니다. 지수법칙에 의하면 N의 100제곱은 N의 50제곱을 다시 제곱한 것과 같습니다. 다시 N의 50제곱은 25제곱을 제곱한 것과 같죠. 25제곱은 12제곱을 제곱한 후 N을 한 번 더 곱해주면 됩니다. 이를 사용하면 100제곱을 100번의 곱셈이 아닌 8번의 곱셈으로 구할 수 있으며, 이 단축 효과는 지수가 크면 클수록 더 극적으로 차이가 나게 됩니다.
def _pow(x: list[int], y: int) -> list[int]:
if y == 0:
return [1]
if y == 1:
return x
w = _pow(x, y // 2)
z = _mul(w, w)
if y % 2 == 0:
return z
return _mul(z, x)