注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

用欧拉定理求在1到n-1内互质数的个数  

2014-05-06 19:23:32|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为Euler's totient function、φ函数、欧拉商数等。
  例如φ(8)=4,因为1,3,5,7均和8互质。
  从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。 
  φ函数的值 
  φ(1)=1(唯一和1互质的数就是1本身)。 
  若n是质数p的k次幂,φ(n)=p^k-p^(k-1)=(p-1)p^(k-1),因为除了p的倍数外,其他数都跟n互质。 
  欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)。
  证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理,A*B和C可建立一一对应的关系。因此φ(n)的值使用算术基本定理便知, 
  若
  n= ∏p^(α(下标p))
  p|n 
  则φ(n)=∏(p-1)p^(α(下标p)-1)=n∏(1-1/p)
  p|n p|n 
  例如φ(72)=φ(2^3×3^2)=(2-1)2^(3-1)×(3-1)3^(2-1)=24
  与欧拉定理、费马小定理的关系 
  对任何两个互质的正整数a, m, m>=2有 
  a^φ(m)≡1(mod m)
  即欧拉定理 
  当m是质数p时,此式则为: 
  a^(p-1)≡1(mod m)
  即费马小定理。

#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
#define N 10000000
 
int main(int argc, const char *argv[])
{
    int *phi;
    char *prime;
    prime = (char*)malloc((N + 1) * sizeof(char));
    prime[0] = prime[1] = 0;
    for(int i = 2; i <= N; i++)
        prime[i] = 1;
    for(int i = 2; i * i <= N; i++)
        if(prime[i])
            for(int j = i * i; j <= N; j += i)
                prime[j] = 0;
    //这段求出了N内的所有素数
    phi = (int*)malloc((N + 1) * sizeof(int));
    for(int i = 1; i <= N; i++)
        phi[i] = i;
    for(int i = 2; i <= N; i++)
        if(prime[i])
            for(int j = i; j <= N; j += i)
                phi[j] = phi[j] / i * (i - 1); //此处注意先/i再*(i-1),否则范围较大时会溢出
    return 0;
}
//这段求出了N内所有数的欧拉函数值



     代码:

#include<stdio.h>
int main()
{int eular(int n);
  int n;
  while(scanf("%d",&n)!=EOF)
   printf("从1到%d上有%d个与%d互质的数\n",n-1,eular(n),n);
return 0;
}


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

  评论这张
 
阅读(1538)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018