初等数论c++VIP专享VIP免费

下载本文档

阅读 59
下载 29
格式 doc
大小 70 KB
约11页
2024-10-17 发布于山西
收藏
评论
点赞(0)
海报
举报

1/11页

2/11页

3/11页

在线预览已结束，请下载后查看完整版，加入VIP享文档下载特权

/11

文本预览下载提示常见问题

备注：纯手写代码，注释。数论1、素数（1）暴力求解法根据素数的概念，没有1和其本身没有其他正因数的数。所以只需枚举比这个数小的数，看能整除即可；C++代码：#include#include#includeusingnamespacestd;booldetermine(intnumber){if(n<=2)returnfalse;if(!n%2)returnfalse;for(inti=3;i<=ceil(sqrt(number));i+=2)//去掉了偶数的判断，效率提高一倍/*如果number整除以i，那么会得到两个的因数，而较小的那个因数不会超过number的二分之一次方；所以只需判断到number的平方根向上取整即可；*/if(number%i);elsereturnfalse;returntrue;}intmain(){intsum;cin>>sum;if(determine(sum))cout<<"YES!";elsecout<<"NO!";return0;}时间复杂度：o(sqrt(n)/2);空间复杂度：几乎没有；（2）一般线性筛法：因为任何一个合数都能分解成几个素数相乘的形式；所以可以做一个表，首先把2设为质数，然后将2的倍数设为合数，剩下的数就是新得到的质数，然后重复这个过程，直到筛到合适的范围即可；但是这个算法有缺陷：1、同一个数可能被筛多次，这就产生了多余的步骤。2、占用空间很大，如果使用bool数组的话，只能筛到1e9；3、从1-n筛，不能从m-n开始筛；C++代码：#include#include#includeusingnamespacestd;bools[1000000000];intm,n;intmain(){cin>>m>>n;memset(s,true,n);s[0]=s[1]=0;//输出M—N之间所有素数；for(inti=2;i<=ceil(sqrt(n));++i)if(s[i]){for(intj=i;j<=n;++j)if(s[i*j])s[i*j]=false;}for(inti=m;i<=n;++i)if(s[i])cout<#include#includeusingnamespacestd;intm,n,sum;boolinp[1000000000];ints[100000000]={0,0};intmain(){cin>>m>>n;for(inti=2;i<=n;++i){if(!inp[i])s[sum++]=i;for(intj=0;j#include#include#include#includeusingnamespacestd;bools[1000000];intm,n,sum=0,num;intPrime[1212121];intzhi[1500];voidPrimes(){for(inti=1;i<=num;++i)s[i]=true;s[0]=s[1]=0;for(inti=2;i<=num;++i)if(s[i]){Prime[++sum]=i;for(intj=i;j<=num;++j)if(s[i*j])s[i*j]=false;}}intmain(){intflag=0;cin>>num;intnumber=num;Primes();if(s[num]){cout<1)for(inti=1;num>1&&i<=sum;++i)if(!(num%Prime[i])){zhi[++flag]=Prime[i];num/=Prime[i];}sort(zhi+1,zhi+flag+1);cout<#include#include#include#includeusingnamespacestd;bools[1000000];intm,n,sum=0,num;intPrime[1212121];...

1、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
3、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。

碎片内容

初等数论c++

您可能关注的文档

文章天下 + 关注: 实名认证
内容提供者

各种文档应有尽有

收藏店铺进入空间

初等数论c++VIP专享VIP免费

初等数论c++

您可能关注的文档

相关文档

热门下载

相关标签