아킬레스 수란?
주어진 양의 정수 n이 아킬레스 수인지 판별하는 것이 이 글의 목표입니다. n이 아킬레스 수라면 'YES'를, 그렇지 않다면 'NO'를 출력해야 합니다.
아킬레스 수: 수학에서 아킬레스 수는 강수(powerful number)이면서 동시에 완전 거듭제곱수가 아닌 수로 정의됩니다. 여기서 강수란, 모든 소인수 p에 대해 p² 역시 그 수를 나누어 떨어지게 하는 수를 의미합니다.
처음 등장하는 아킬레스 수들은 다음과 같습니다.
72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125
예시
입력 − 108
출력 − YES
108은 6과 36 모두로 나누어 떨어지므로 강수이며, 완전 제곱수가 아니기 때문에 아킬레스 수에 해당합니다.
입력 − 64
출력 − NO
설명 − 64는 강수이지만 2⁶ = 64로 완전 거듭제곱수이므로 아킬레스 수가 아닙니다.
풀이 접근 방법
- 주어진 수 N이 강수인지 먼저 확인합니다.
- N이 완전 거듭제곱수인지 확인합니다.
- N이 강수이면서 완전 거듭제곱수가 아니라면 N은 아킬레스 수입니다. 그렇지 않으면 아닙니다.
C++ 구현 예제
// C++ 프로그램: 아킬레스 수 판별
#include <bits/stdc++.h>
using namespace std;
// 강수 여부를 확인하는 함수
bool isPowerful1(int n1){
while (n1 % 2 == 0) {
int power1 = 0;
while (n1 % 2 == 0) {
n1 /= 2;
power1++;
}
if (power1 == 1)
return false;
}
for (int factor1 = 3; factor1 <= sqrt(n1); factor1 += 2) {
int power1 = 0;
while (n1 % factor1 == 0) {
n1 = n1 / factor1;
power1++;
}
if (power1 == 1)
return false;
}
return (n1 == 1);
}
// 완전 거듭제곱수 여부를 확인하는 함수
bool isPower1(int a1){
if (a1 == 1)
return true;
for (int i1 = 2; i1 * i1 <= a1; i1++) {
double val1 = log(a1) / log(i1);
if ((val1 - (int)val1) < 0.00000001)
return true;
}
return false;
}
// 아킬레스 수 판별 함수
bool isAchillesNumber1(int n1){
if (isPowerful1(n1) && !isPower1(n1))
return true;
else
return false;
}
// 드라이버 코드
int main(){
int n1 = 108;
if (isAchillesNumber1(n1))
cout << "YES" << endl;
else
cout << "NO" << endl;
n1 = 35;
if (isAchillesNumber1(n1))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}코드 설명
isPowerful1() 함수는 소인수분해를 진행하면서 각 소인수의 지수가 2 이상인지 검사하여 강수 여부를 판별합니다. 지수가 정확히 1인 소인수가 하나라도 존재하면 강수가 아니므로 false를 반환합니다.
isPower1() 함수는 로그 연산을 활용해 해당 수가 어떤 정수의 거듭제곱 형태로 표현될 수 있는지 확인합니다. 오차 범위 0.00000001 이내에서 로그 값이 정수가 되면 완전 거듭제곱수로 판단합니다.
isAchillesNumber1() 함수는 위 두 조건을 결합하여, 강수이면서 완전 거듭제곱수가 아닌 경우에만 true를 반환함으로써 아킬레스 수를 최종 판별합니다.
출력 결과
YES NO
108은 아킬레스 수이므로 'YES'가 출력되고, 35는 소인수 5와 7의 지수가 각각 1이라 강수 조건을 만족하지 못하므로 'NO'가 출력됩니다.