이 글에서는 분자를 저장할 정수 a_num과 반드시 소수여야 하는 분모 p_den이 주어졌을 때, a_num을 p_den으로 나눈 결과에 대해 미디의 정리(Midy's Theorem)가 성립하는지 확인하는 방법을 다룹니다.
미디의 정리 증명 절차
분자 a_num과 항상 소수 값이어야 하는 분모 p_den을 입력받습니다.
두 수를 나누고 순환소수(반복되는 소수 자릿수)를 확인합니다.
소수 자릿수가 반복되기 시작할 때까지 값을 저장합니다.
자릿수 개수가 짝수인지 확인하고, 짝수라면 두 부분으로 나눕니다.
나눈 두 수를 더합니다. 그 결과가 모든 자리가 9인 문자열이라면 미디의 정리가 성립함을 증명한 것입니다.
입력 및 출력 예제
입력 — int a_num = 1, int p_den = 19
출력 — 순환소수: 052631578947368421 / 미디의 정리 성립
설명 — 위에서 언급한 단계에 따라 미디의 정리를 확인해 보겠습니다.
1 ÷ 19 = 0.052631578947368421...
순환소수는 052631578947368421입니다.
자릿수를 두 부분으로 나누면 052631578 과 947368421이 됩니다.
두 부분을 더하면 052631578 + 947368421 = 999999999입니다.
결과가 9로만 이루어진 문자열이므로 미디의 정리가 성립함을 알 수 있습니다.
입력 — int a_num = 49, int p_den = 7
출력 — 순환소수 없음
설명 — 49는 7로 완전히 나누어떨어지므로 소수 값이 발생하지 않습니다. 따라서 출력은 "순환소수 없음"이 됩니다.
프로그램에서 사용된 접근 방식
정수 값 a_num과 p_den을 입력받습니다.
미디의 정리를 증명하기 위해 Midys_theorem(a_num, p_den) 함수를 호출합니다.
check_Midys() 함수 내부에서는:
int first = 0, int last = 0 변수를 생성합니다.
check(val) 함수가 FALSE를 반환하면 "미디의 정리 적용 불가"를 출력합니다.
그렇지 않고 len % 2 == 0이라면, i가 0부터 len/2보다 작을 때까지 반복하면서 first = first * 10 + (str[i] - '0')과 last = last * 10 + (str[len / 2 + i] - '0')을 계산하고 "미디의 정리 성립"을 출력합니다.
위 조건에 해당하지 않으면 "미디의 정리 적용 불가"를 출력합니다.
Midys_theorem(int a_num, int p_den) 함수 내부에서는:
map<int, int> 타입의 map_val 변수를 생성하고 초기화(clear)합니다.
reminder를 a_num % p_den으로 설정합니다.
reminder가 0이 아니고 map_val.find(reminder)가 map_val.end()와 같지 않은 동안, map_val[reminder]에 result.length()를 저장하고, reminder에 10을 곱한 뒤, temp = reminder / p_den을 계산하여 result에 추가하고, reminder = reminder % p_den으로 갱신합니다.
remainder가 0이면 "-1"을 반환하고, 그렇지 않으면 count를 result.substr(map_val[reminder])로 설정합니다.
count를 반환합니다.
bool check(int val) 함수 내부에서는:
i가 2부터 val/2까지 반복하며, val % i == 0이면 FALSE를 반환하고, 반복이 끝나면 TRUE를 반환하여 소수 여부를 판별합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
bool check(int val){
for(int i = 2; i <= val / 2; i++){
if(val % i == 0){
return false;
}
}
return true;
}
void check_Midys(string str, int val){
int len = str.length();
int first = 0;
int last = 0;
if(!check(val)){
cout<<"\nNot applicable for Midy's theorem";
}
else if(len % 2 == 0){
for(int i = 0; i < len / 2; i++){
first = first * 10 + (str[i] - '0');
last = last * 10 + (str[len / 2 + i] - '0');
}
cout<<"\nProved Midy's theorem";
}
else{
cout<<"\nNot applicable for Midy's theorem";
}
}
string Midys_theorem(int a_num, int p_den){
string result;
map<int, int> map_val;
map_val.clear();
int reminder = a_num % p_den;
while((reminder != 0) && (map_val.find(reminder) == map_val.end())){
map_val[reminder] = result.length();
reminder = reminder * 10;
int temp = reminder / p_den;
result += to_string(temp);
reminder = reminder % p_den;
}
if(reminder == 0){
return "-1";
}
else{
string count = result.substr(map_val[reminder]);
return count;
}
}
int main(){
int a_num = 1;
int p_den = 19;
string result = Midys_theorem(a_num, p_den);
if(result == "-1"){
cout<<"No Repeating Decimal";
}
else{
cout<<"Repeating decimals are: "<<result;
check_Midys(result, p_den);
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Repeating decimals are: 052631578947368421 Proved Midy's theorem
참고로 미디의 정리란, 소수 p로 나눈 분수의 순환소수 자릿수가 짝수일 때, 이를 두 부분으로 나누어 더하면 반드시 9로만 이루어진 수가 된다는 정리입니다. 예를 들어 1/19의 경우처럼 이 프로그램은 나눗셈 연산을 통해 순환절(순환 구간)을 추출하고, 이를 검증하는 과정을 효율적으로 구현한 것입니다.