首页 > 代码库 > 【数学】素数相关算法、结论总结
【数学】素数相关算法、结论总结
弱菜开始学数论了，不定时更新。。。
一.素数定理：
素数分布：小于x的素数大约有 x/ln(x)个
推论：如果Pn为第n个素数 那个Pn约等于n*ln(n);
二.素数测试
1.sqrt(n)的朴素测试。这个就不多说了，数据范围小的时候比较方便
2.nlogn的筛法
void setprime() { memset(prime, 0, sizeof(prime)); //为了方便赋值。令prime[i]=0 表示 i是素数 for (int i=2; i<N; i++) if (!prime[i]) { for (int k=i*i; k<N; k+=i) prime[k]=1; } return;}
3.线性筛
2中筛法会重复筛掉部分合数，因此复杂度还可以优化，得到线性筛
void setprime() { for(long i = 2 ; i < N ; i ++) { if(! isNotPrime[i]) prime[num_prime ++]=i; for(long j = 0 ; j < num_prime && i * prime[j] < N ; j ++) { isNotPrime[i * prime[j]] = 1; if( !(i % prime[j] ) ) break; //关键优化 } } return ; }
此筛法的关键在于注释中的break。prime[]数组记录素数。当i可以整除prime[j]的时候break，原理见 http://blog.csdn.net/leolin_/article/details/6642126
2,3中的筛法单独使用都只能筛出较小范围的素数，范围较大，如1e9时，数组开不了，时间也是不允许的
4.改进的筛法素数测试
此方法是2.3中方法的应用和延伸，用来筛超大范围的质数。。由1中朴素判断法我们可以知道，判断素数只需要判断sqrt范围内有没有因子即可，所以在范围变大的时候，我们可以先用筛法筛出
sqrt（n）中的素数并保存在数组中。范围1e9的话只需要筛出30000多内的素数即可，再用保存下来的素数去对更大范围的数进行素数测试。如poj2689（最大所测试数达到了2147483647）
就是这种方法的直接应用
AC代码：
#include<stdio.h>#include<string.h>#include <algorithm>using namespace std;#define N 100007bool isprime0[50000];int prime0[50000];long long prime[100000];bool isprime[1000010];int num0;int num;long long x,y;void setprime(){ num=0; for(int i=2;i<=50000;i++) { if(!isprime0[i]) prime0[num0++]=i; for(int j=0;j<num0&&prime0[j]*i<=50000;j++) { isprime0[i*prime0[j]]=1; if(!(i%prime0[j])) break; } }}void setprime1(){ memset(isprime,0,sizeof(isprime)); for(int i=0;i<num0;i++) { long long j=x/prime0[i]; while(j*prime0[i]<x) j++; for(j=j*prime0[i];j<=y;j+=prime0[i]) if(j/prime0[i]>1) isprime[j-x]=1; } if(x==1) isprime[0]=1; num=0; for(long long i=0;i<=y-x;i++) { if(!isprime[i]) prime[num++]=x+i; }}int main(){ setprime(); while(scanf("%I64d%I64d",&x,&y)!=EOF) { setprime1(); long long a,b,c,d; long long mi=10000000,ma=0; if(num<2) { puts("There are no adjacent primes."); continue; } for(int i=0;i+1<num;i++) { long long p=prime[i+1]-prime[i]; if(p<mi) { a=prime[i]; b=prime[i+1]; mi=p; } if(p>ma) { c=prime[i]; d=prime[i+1]; ma=p; } } printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",a,b,c,d); } return 0;}
【数学】素数相关算法、结论总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。