数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找素数模的原根数量。
在这个问题中，我们给定一个素数 N。我们的任务是查找素数模的原根数量。
数字的原根 - 它是一个小于 N 的数字 (r)，对于 [0, n-2] 范围内的所有 X，它都具有所有不同的 r^x(mod N) 值。
让我们举个例子来理解这个问题，
Input : N = 5 Output : 2
解决方案方法
解决此问题的一个简单方法是基于试探法。我们将检查从 2 到 (N-1) 的所有数字，以满足 x 范围为 [0, n-2] 的条件，并在找到满足条件的值时中断。
这种解决方案很简单，易于实现，但解决方案的时间复杂度为 N2 阶。如果 N 的值很大，这可能会导致运行时间过长。
因此，解决此问题的一个更有效的解决方案是使用欧拉函数 φ(N)
因此，对于一个数字 r 成为 N 的原根。它对 N 的模的乘法阶数等于 φ(N)。以下是需要遵循的步骤 -
我们需要找到素数 N 的 (N-1) 的所有素数因子。然后使用 (N-1) / 素数因子计算所有幂。然后检查素数幂模 n 的值。如果它永远不为 1，则 i 是原根。我们看到的第一个值将作为返回值，因为一个数字可能有多个原根，但我们只需要最小的一个。
示例
让我们举个例子来理解这个问题
#include<bits/stdc++.h>
using namespace std;
int calcPowerMod(int x, unsigned int y, int p){
int modVal = 1;
x = x % p;
while (y > 0){
if (y & 1)
modVal = (modVal*x) % p;
y = y >> 1;
x = (x*x) % p;
}
return modVal;
}
void findAllPrimeFactors(unordered_set<int> &s, int n){
while (n%2 == 0){
s.insert(2);
n = n/2;
}
for (int i = 3; i*i <= n; i = i+2){
while (n%i == 0){
s.insert(i);
n = n/i;
}
}
if (n > 2)
s.insert(n);
}
int findSmallestPrimitiveRoot(int n){
unordered_set<int> primes;
int phi = n-1;
findAllPrimeFactors(primes, phi);
for (int r=2; r<=phi; r++){
bool flag = false;
for (auto it = primes.begin(); it != primes.end(); it++){
if (calcPowerMod(r, phi/(*it), n) == 1){
flag = true;
break;
}
}
if (flag == false)
return r;
}
return -1;
}
int main(){
int n = 809;
cout<<"The smallest primitive root is "<<findSmallestPrimitiveRoot(n);
return 0;
}输出
The smallest primitive root is 3
更新于： 2022年1月24日
584 次查看
广告