Untitled
unknown
plain_text
5 months ago
1.8 kB
3
Indexable
#include <iostream> #include <vector> using namespace std; int power(int a, int b, int m) { int result = 1; a = a % m; while (b > 0) { if (b % 2 == 1) { result = (result * a) % m; } a = (a * a) % m; b = b / 2; } return result; } int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } vector<int> findPrimitiveRoots(int n) { vector<int> primitiveRoots; for (int r = 2; r < n; r++) { if (gcd(r, n) == 1) { bool isPrimitiveRoot = true; for (int i = 1; i < n - 1; i++) { if (power(r, i, n) == 1) { isPrimitiveRoot = false; break; } } if (isPrimitiveRoot && power(r, n-1, n) == 1) { primitiveRoots.push_back(r); } } } return primitiveRoots; } int main() { int n; do { cout << "Enter a positive integer: "; cin >> n; vector<int> primitiveRoots = findPrimitiveRoots(n); if (primitiveRoots.empty()) { cout << "No primitive roots found for " << n << endl; } else { cout << "Primitive roots of " << n << " are: "; for (int root : primitiveRoots) { cout << root << " "; } cout << endl; } cout << "Do you want to continue? (y/n): "; char ch; cin >> ch; if (ch == 'n' || ch == 'N') { break; } } while (true); return 0; }
Editor is loading...
Leave a Comment