锐客网

  1. 首页 > 生活百科 > it技术 > >

欧拉函数c语言原理 欧拉公式的c语言实现( 二 )

IT技术函数


具体代码：
#includeiostream
using namespace std;
int n;
int main(){
cinn;
while(n--){
int x;
cinx;
int res=x;
for(int i=2;i=x/i;i++){
if(x%i==0){
while(x%i==0){
x=x/i;//i是我的一个质数
}
res=res/i*(i-1);
}
}
if(x1) res=res/x*(x-1);//注意
coutresendl;
}
}
二.筛法求欧拉函数
1.算法描述
第一部分中的算法适合于求单个给定数字对应的欧拉函数的值，但是当题目要求求1~N所有数字的欧拉值之和时，用第一部分中的算法就会花费很多时间 ， 下介绍用筛法求欧拉函数：
首先我们回顾筛法求质数的过程，对于给定的正整数N：
for(int i=2;i=n;i++){
if(!str[i]){
primes[cnt++]=i;
}
else{
for(int j=0;primes[j]=n/i;j++){
str[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
通过筛法，所有的质数，合数我们都可以遍历到，把所有的质数加入数组primes中，并且str[i*primes[j]]保证了每一个数都会被它的最小质因子筛掉，而if(i%primes[j]==0)保证了不会被重复标记 ， 详细介绍可以参考：
那如何做出修改让筛法求欧拉函数？
1.首先，对于质数i，那么1~i-1都与i互质，那么\phi \left (i \right )=i-1
2.对于合数，即我用str[i*primes[j]]将一个合数筛掉时，我必须同时把它的欧拉值求出来 ， 我们分为以下两种情况：
A.若i可以整除primes[j]，那么primes[j]*i和i有共同的质因子，这是因为primes[j]是i的质因子，那么\phi \left ( i \right )已经包括了1-\frac{1}{primes[j]}这一项，而欧拉函数的值与指数无关，因而：
\phi \left ( i*primes[j] \right )=primes[j]*\phi \left ( i \right )
B.若i不能够整除primes[j] ， 那么primes[j]*i比i多一个质因子primes[j]，这是因为i本身不包含质因子primes[j]，而primes[j]本身是质数，不会再有质因子，因而：
\phi \left ( i*primes[j] \right )=primes[j]\left ( 1-\frac{1}{primes[j]} \right )\phi \left ( i\right )=\left ( primes[j] -1\right )\phi \left ( i \right )
因而，每一个数的欧拉值都可以通过该种方法求出来 。
2.代码实现
关于代码实现需要注意的是 ， res的值可能会很大，所以要定义成long long类型 。
具体代码：
#includeiostream
using namespace std;
int x;
const int N=1000010;
long long res;//最后的欧拉函数的值的和，有可能会非常大，要用long long
bool str[N];//是否被标记过
int primes[N];//存放质因子
int cnt;
int phi[N];//各个N的函数值
int main(){
phi[1]=1;//1的欧拉值为1捏
cinx;
for(int i=2;i=x;i++){
if(!str[i]){//如果没有被标记过 ， 那么是质数
phi[i]=i-1;//质数的欧拉值就是i-1
primes[cnt++]=i;
}
for(int j=0;primes[j]=x/i;j++){
str[i*primes[j]]=true;//首先我一定能把所有的合数遍历到，这是肯定的
if(i%primes[j]==0){
//如果i可以整除primes[j]的话,那么i和primes[j]*i的最小质因子是相同的
phi[i*primes[j]]=primes[j]*phi[i];
break;
}
else{
//如果i不可整除primes[j]的话，那么i和primes[j]*i就相差一个primes[j]这个最小质因子
phi[i*primes[j]]=primes[j]*phi[i]*(primes[j]-1)/primes[j];
//那这样就把所有数的欧拉值都存在phi中
}
}
}
for(int i=1;i=x;i++){
res=res+phi[i];
}
coutres;
}
欧拉定理欧拉定理
对于互质的整数a和n，有a^φ(n) ≡ 1 (mod n)
证明：
首先证明下面这个命题：
对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是φ(n)个n的素数，且两两互素，即n的一个化简剩余系，或称简系，或称缩系) ， 考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)}

推荐阅读


上一篇：redis有大量timewait连接，redis连接时间和超时时间多少合理

下一篇：角色扮演游戏书屋教案，角色扮演游戏教案设计意图