백준 4355번 서로소 - C++ 풀이

---

 

1. N을 소인수 분해한다.
2. 오일러 피 함수를 사용하여 서로소의 개수를 구한다.

 

1. N을 소인수 분해한다.

 오일러 피 함수를 사용할 것이다. 이를 위해 N의 소인수를 모두 구해둔다.

 

2. 오일러 피 함수를 사용하여 서로소의 개수를 구한다.

 N과 서로소인 1부터 N까지의 정수의 개수를 구하는 함수인 오일러 피 함수를 이용하여 서로소의 개수를 구한다.

 

반응형

---

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

// 소인수분해
vector<int> calcDivisors(int N) {
    vector<int> divisors;
    int n = N;
    
    for (int i=2; i*i<=N; i++) {
        if (n % i == 0) divisors.push_back(i);
        while (n % i == 0) n /= i;
    }
    
    if (n > 1) divisors.push_back(n);
    
    return divisors;
}

int countCoprime(int N) {
    vector<int> divisors = calcDivisors(N);
    int coprimeCnt = N;
    
    for (auto d: divisors) {
        coprimeCnt /= d;
        coprimeCnt *= d-1;
    }
    
    return coprimeCnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    
    while (true) {
        int N; cin >> N;
        if (N == 0) break;
        
        cout << countCoprime(N) << "\n";
    }

    return 0;
}