어떤 수 n이 주어졌을 때, n이 아킬레스 수(Achilles number)인지 판별해야 합니다. 아킬레스 수란 강력수(powerful number)이면서 동시에 완전거듭제곱(perfect power)은 아닌 수를 말합니다.
여기서 강력수란 모든 소인수 p에 대해 p² 역시 그 수를 나누는 수를 의미합니다. 아킬레스 수의 대표적인 예로는 72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125 등이 있습니다.
예를 들어 입력이 108이라면 결과는 True입니다. 6과 36이 모두 108을 나누므로 강력수 조건을 만족하지만, 완전제곱수는 아니기 때문입니다.
해결 접근 방법
이 문제는 다음 두 가지 검사 함수를 정의하고 조합하여 해결할 수 있습니다.
1. check_powerful() 함수 — 강력수 여부 검사
- n이 짝수인 동안 다음을 반복합니다.
- p := 0으로 초기화
- n이 2로 나누어떨어지는 동안 n을 2로 나누고 p를 1씩 증가
- p가 1이면(즉, 2가 한 번만 곱해진 경우) False 반환
- p := int(sqrt(n)) + 1로 설정
- factor를 3부터 p까지 2씩 증가시키며 반복합니다.
- p := 0으로 초기화
- n이 factor로 나누어떨어지는 동안 n을 factor로 나누고 p를 1씩 증가
- p가 1이면 False 반환
- 마지막으로 n이 1이면 True, 아니면 False 반환
2. check_power() 함수 — 완전거듭제곱 여부 검사
- a가 1이면 True 반환
- i를 2부터 a-1까지 1씩 증가시키며 반복합니다.
- val := log(a) / log(i) (자연로그 기준)
- val의 소수 부분이 0.00000001보다 작으면 True 반환
- 반복이 끝나면 False 반환
3. 최종 판별 로직
- check_powerful(n)이 True이고 check_power(n)이 False이면 → True 반환 (아킬레스 수)
- 그렇지 않으면 → False 반환
구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
from math import sqrt, log def check_powerful(n): while (n % 2 == 0): p = 0 while (n % 2 == 0): n /= 2 p += 1 if (p == 1): return False p = int(sqrt(n)) + 1 for factor in range(3, p, 2): p = 0 while (n % factor == 0): n = n / factor p += 1 if (p == 1): return False return (n == 1) def check_power(a): if (a == 1): return True p = int(sqrt(a)) + 1 for i in range(2, a, 1): val = log(a) / log(i) if ((val - int(val)) < 0.00000001): return True return False def isAchilles(n): if (check_powerful(n) == True and check_power(n) == False): return True else: return False n = 108 print(isAchilles(n))
입력
108
출력
True
정리
아킬레스 수 판별은 크게 두 단계로 나뉩니다. 첫째, 소인수분해를 통해 각 소인수가 최소 제곱 형태(p²)로 포함되어 있는지 확인하여 강력수 여부를 검사합니다. 둘째, 로그 연산을 활용해 해당 수가 어떤 정수의 거듭제곱과 일치하는지 확인하여 완전거듭제곱 여부를 검사합니다. 두 조건을 모두 만족하는 경우에만 그 수를 아킬레스 수로 판정할 수 있습니다.