[4355번] 서로소 - 오일러 파이 함수[C++]

http://min92.tistory.com/70

오일러 파이 함수를 통해서 풀면

파이는 1~n까지의 수 중에서 n과 서로소인 수의 갯수이다.

#include <cstdio>
#include <iostream>
#include <math.h>
 
using namespace std;
 
int prime[50];
int primeCopy[50];
 
int primeCopy2[50];
int primeCopyPower[50];
 
void function(int firstInputNumber)
{
    int i, primeIndex, inputNumber;
    int x;
    primeIndex = 0;
    inputNumber = firstInputNumber;
    
    //소인수분해
    for(i = 2; i < inputNumber; i++)
    {
        if(inputNumber % i == 0)
        {
            prime[primeIndex] = i;
            primeIndex++;
            inputNumber /= i;
            i = 1;
        }
    }
    
    x = inputNumber;
    
    i = 0;
    
    while(firstInputNumber != x)
    {
        x = x * prime[i];
        i++;
    }
    prime[i] = inputNumber;
    
    //primeCopy에는 소인수분해해서 최소공배수들이 모임
    for(int j = 0; j <= i; j++){
        primeCopy[j] = prime[j];
    }
    
    //primeCopy2에는 소인수분해해서 최소공배수가 중복되지 않게 넣음
    //primeCopyPower에는 각자의 최소공배수가 몇 개씩 있는지를 넣음
    int k = 0;
    for(int j = 0; primeCopy[j] != 0; j++){
        if(j != 0){
            if(primeCopy[j] == primeCopy[j-1]){
                primeCopyPower[k]++;
            }else{
                k++;
                primeCopyPower[k]++;
                primeCopy2[k] = primeCopy[j];
            }
        }
        else{
            primeCopyPower[k]++;
            primeCopy2[k] = primeCopy[j];
        }
    }
}
 
int main(){
    int N;
    int result = 1;
    
    while(1){
        cin >> N;
        if(N == 0) break;
        
        //initialization
        for(int k = 0; k < 50; k++){
            prime[k] = 0;
            primeCopy[k] = 0;
            primeCopy2[k] = 0;
            primeCopyPower[k] = 0;
            result = 1;
        }
        
        function(N);
        
        //오일러의 파이 함수 정리
        for(int j = 0; primeCopy2[j] != 0; j++){
            result *= pow(primeCopy2[j], primeCopyPower[j]) - pow(primeCopy2[j], primeCopyPower[j]-1);
        }
        printf("%d\n", result);
    }
    
    return 0;
}