오일러 파이 함수(Eulerφ函數: Euler’s phi (totient) function) 구현

문제). 
오일러 파이 함수(Eulerφ函數: Euler’s phi (totient) function)를 구현하시오.

 

수론에서 오일러 파이 함수(Eulerφ函數, 영어: Euler’s phi (totient) function)는 정수환의 몫환의 가역원을 세는 함수이다. 즉, n이 양의 정수일 때, φ(n)은 n과 서로소인 1부터 n까지의 정수의 개수와 같다. 예를 들어, 1부터 6까지의 정수 가운데 1, 5 둘만 6과 서로소이므로, ϕ(6) = 2이다. 1부터 10까지의 정수는 모두 11과 서로소이며, 11은 자기 자신과 서로소가 아니므로, φ(11) = 10이다. 1은 자기 자신과 서로소이므로, φ(1) = 1이다.

--출처:위키백과--

 

---

 

실행 예1).

 

입력)

value : 20

 

결과).

φ(5) = 8

 

 

---

 

 

실행 예2).

 

입력)

value : 11

 

결과).

φ(11) = 10

 

 

 

 

 

 

 

 

 

 

 

---

답은 아래에... ↓

 

 

 

 

 

 

 

---

 

 

 

 

 

스스로 풀어보시고... ↓

 

 

 

 

 

 

---

 

 

 

 

 

 

아래 답과 비교해보세요. ↓

 

 

 

 

 

 

---

프로그램 소스

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>


/* 두 수의 최대 공약수 */
static int GDC(int x, int y)
{
    if(y == 0) {
        return x;
    }
    return GDC(y, x % y);
}

/* φ()함수 구현 */
int euler_phi(int value)
{
    int idx;
    int count = 1;
    
    if(value <= 0) {
        return -1;
    }
    
    for(idx = 2; idx < value; idx++) {
        if(GDC(idx, value) == 1) {
            count++;
        }
    }
    return count;
}

int main(void)
{
    int value;
    
    printf("value : ");
    scanf("%d", &value);
    
    printf("φ(%d) = %d\n", value, euler_phi(value));
    
    return 0;
}