C ++中质数n为模n的素数根
在这个问题中，给我们一个质数N。我们的任务是打印以N为模的质数N的原始根。
素数N的素数根是位于[1，n-1]之间的整数x，因此k位于[0，n-2]的xk（modn）的所有值都是唯一的。
让我们举个例子来了解这个问题，
Input: 13 Output: 2
为了解决这个问题，我们必须使用称为Euler的Totient函数的数学函数。
欧拉的Totient函数是从1到n的数字的计数，这些数字相对于n为质数。
如果GCD(i,n)=1，则数字i相对质数。
在解决方案中，如果x模n的乘法阶等于Euler的Totient函数，则该数字为原始根，否则为原始根。我们将检查所有相对素数。
注意：素数n=n-1的欧拉Totient函数
以下代码将显示我们解决方案的实现，
示例
#include<bits/stdc++.h>
using namespace std;
bool isPrimeNumber(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
int power(int x, unsigned int y, int p) {
int res = 1;
x = x % p;
while (y > 0){
if (y & 1)
res = (res*x) % p;
y = y >> 1;
x = (x*x) % p;
}
return res;
}
void GeneratePrimes(unordered_set<int> &s, int n) {
while (n%2 == 0){
s.insert(2);
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i+2){
while (n%i == 0){
s.insert(i);
n = n/i;
}
}
if (n > 2)
s.insert(n);
}
int findPrimitiveRoot(int n) {
unordered_set<int> s;
if (isPrimeNumber(n)==false)
return -1;
int ETF = n-1;
GeneratePrimes(s, ETF);
for (int r=2; r<=ETF; r++){
bool flag = false;
for (auto it = s.begin(); it != s.end(); it++){
if (power(r, ETF/(*it), n) == 1){
flag = true;
break;
}
}
if (flag == false)
return r;
}
return -1;
}
int main() {
int n= 13;
cout<<" Smallest primitive root of "<<n<<" is "<<findPrimitiveRoot(n);
return 0;
}输出结果
Smallest primitive root of 13 is 2