欧拉函数+素数筛
2018-06-17 23:51:29来源:未知 阅读 ()
欧拉函数,就是欧拉发现的一个关于求素数的的公式,然后我们编个函数实现这个公式。
欧拉发现求小于等于n的正整数中有多少个数与n互质可以用这个公式:
euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数,x是不为0的整数。euler(1)=1(唯一和1互质的数就是1本身)。
欧拉公式的延伸:一个数的所有质因子之和是euler(n)*n/2。
其实直接看模板加注解想想就能看懂
筛选的原理就是找出n的因子,剔除含有n的因子的数,即剔除与n不互质的数
既然是求与n互质的个数,那我们可以直接筛选,看模板:
int phi(int n)
{ int res=n; /假设现有n个数与n互质,开始筛选剔除
for(i=2;i*i<=n;i++)
{ if(n%i==0) /若这个数是n的因子,减去n以下含有这个因子的数个数,假设n=8,小于等于8,2为公因子的有8/2=4个
{ res-=res/i;
while(n%i==0) /将n不断整除这个因子
n=n/i;
}
}
if(n>1) /若n大于1,则此时的n也是一个除1以外的因子
res-=res/n;
return res;
}
有时候还用到多个数的欧拉值,因此需要对1到n的数都求出欧拉值,就是打表。
将1到n的欧拉值求出并存储到数组,筛选法,代码:
void phi(int n) 上边的看懂了,下边这个求多个数的也类似
{ for(int i=1;i<=n;i++)
p[i]=i; 赋原值
for(int i=2;i<=n;i++)
if(p[i]==i)
{ for(int j=i;j<=n;j+=i) 筛选
p[j]=p[j]-p[j]/i;
}
}
素数筛:就是让你判断任意一个数是否为素数,若问一个求一个显然会超时,所以首先需要把素数都求出来,用筛选法求的,所以叫素数筛。
原理就是若一个数有除1和它本身以外的因子就将它标记不是素数,最后无标记的就是素数。
直接看代码加注解:
#include <iostream>
#include <cstring>
#define MAX 1000001
int flag[MAX];
int main()
{ memset(flag,0,sizeof(flag));
flag[1]=1; /1代表不是素数,0代表是素数
for(int i=4;i<MAX;i+=2)
flag[i]=1; /先将偶数先标记不是
for(int i=3;i*i<MAX;i+=2)
for(int j=i*i;j<MAX;j+=i) /奇数的倍数标记不是
flag[j]=1;
int n;
while(cin>>n)
{ if(flag[n]==0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
素数筛常用于让你判断大量素数,或求大量素数,当然如果数目很少,就按常规判断就好了
待续……
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ const成员函数 2020-06-03
- C++ 析构函数 2020-06-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash