Untitled

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;


int euler_totient(int n) {
    int result = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i;
        }
    }
    if (n > 1) {
        result -= result / n;
    }
    return result;
}

bool is_primitive_root(int g, int n) {
    int phi_n = euler_totient(n);
    
   
    vector<int> divisors;
    for (int i = 1; i * i <= phi_n; ++i) {
        if (phi_n % i == 0) {
            divisors.push_back(i);
            if (i != phi_n / i) {
                divisors.push_back(phi_n / i);
            }
        }
    }

   
    for (int i = 0; i < divisors.size(); ++i) {
        int d = divisors[i];
        
        if (d == phi_n) continue;
        
      
        if (pow(g, d) - (int)pow(g, d) / n == 1) {
            return false;
        }
    }
    return true;
}


int main() {
    int n, g;
    
    cout << "Enter modulus n: ";
    cin >> n;
    cout << "Enter candidate g: ";
    cin >> g;
    
    if (is_primitive_root(g, n)) {
        cout << g << " is a primitive root modulo " << n << endl;
    } else {
        cout << g << " is not a primitive root modulo " << n << endl;
    }
    
    return 0;
}