素数

什么是素数就不用多说了吧~~

素数定理：设小于正实数n的素数有f(n)个，f(n)≈n/ln(n)。

推论：令p_n是第n个素数，其中n是正整数，那么p_n≈n×ln(n)。

定理：对于任意的正整数n，至少存在n个连续的正合数。

关于素数的猜想：

1、伯特兰猜想：对于任意给定的正整数n，其中n>1，都存在一个素数p，使得n<p<2n。（切比雪夫已证明）

2、孪生素数猜想：存在无穷多的形如p和p+2的素数对。（陈景润已证明）

3、哥德巴赫猜想：每个大于2的正偶数都可以写成两个素数的和。（已验证所有小于4×10¹⁴的偶数都满足这个猜想）

4、n²+1猜想：存在无穷多个形如n²+1的素数，其中n是正整数。

素数测试：

1、埃拉托色尼筛法

基本素数判别法：正整数n是素数，当且尽当它不能被任何一个小于√n的素数整除。

定理：如果n是一个合数，那么n一定有不超过√n的素因子。

 1 //pri[i]为0的i是素数
 2     int pri[maxn];
 3     memset(pri,0,sizeof(pri));
 4     pri[0]=pri[1]=1;
 5     for(int i=2;i*i<maxn;i++){
 6         if(!pri[i]){
 7             for(int j=i*i;j<maxn;j+=i){
 8                 pri[j]=1;
 9             }
10         }
11     }

埃拉托色尼筛法

2、6N+1法

所有的素数都可以表示成6N±1的形式

注：当n过大时，可以先求出小于√n的素数表，然后用基本素数判别法判断。

例题 POJ - 2689

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 #define CLR(m,a) memset(m,a,sizeof(m))
 6 #define LL long long
 7 const int maxn=50010;
 8 const int inf=0x3f3f3f3f;
 9 int prepri[maxn],vis[maxn*20];
10 int cnt=0;
11 int pri[maxn*20];  //存L到R之间的素数
12 
13 void init()
14 {
15     CLR(vis,1);
16     cnt=0;
17     for(LL i=2;i<maxn;i++)if(vis[i]){
18         prepri[cnt++]=i;
19         for(LL j=i*i;j<maxn;j+=i) vis[j]=0;
20     }
21 }
22 
23 int main()
24 {
25     LL L,R;
26     while(scanf("%lld%lld",&L,&R)!=EOF){
27         init();
28         CLR(vis,1); //假设全是素数
29         for(int i=0;i<cnt;i++){
30             LL b=L/prepri[i];
31             while(b*prepri[i]<L||b<=1) b++;  //小于L的不用管
32             for(LL j=b*prepri[i];j<=R;j+=prepri[i])if(j>=L){
33                 vis[j-L]=0;
34             }
35             if(L==1) vis[0]=0;  //1不是素数
36         }
37         LL minn=inf,maxx=-inf;
38         LL x1,y1,x2,y2;
39         int prict=0;
40         for(int i=0;i<=R-L;i++) if(vis[i])
41             pri[prict++]=L+i;
42         if(prict<=1) puts("There are no adjacent primes.");
43         else {
44             for(int i=1;i<prict;i++){
45                 if(pri[i]-pri[i-1]<minn){
46                     minn=pri[i]-pri[i-1];
47                     x1=pri[i-1];y1=pri[i];
48                 }
49                 if(pri[i]-pri[i-1]>maxx){
50                     maxx=pri[i]-pri[i-1];
51                     x2=pri[i-1];y2=pri[i];
52                 }
53             }
54             printf("%lld,%lld are closest, %lld,%lld are most distant.
",x1,y1,x2,y2);
55         }
56 
57     }
58     return 0;
59 }

基本素数判别法

基本算术定理：

　　每个大于1的正整数n都可以唯一地被写成素数的乘积，在乘积中的素因子按照非降序排列。

性质：

　　1、若n的标准素因子分解表达式为n=p₁^a₁+p₂^a₂+……+p_n^a_n,设d(n)为n的正因子个数，Φ(n)为n的所有因子之和

　　　　则d(n)=(a₁+1)×(a₂+1)×……×(a_n+1)，Φ(n)= 可以用数列求和公式

　　2、n!的素因子分解中素数p的幂为[n/p]+[n/p²]+[n/p³]+……

编辑公式好麻烦，就写这两个吧。。。

例题nefu118，计算n!后面有多少个0。按照公式2，计算素数5的幂即可（因为2的幂一定大于5的幂）。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int main(){
 5     int m;
 6     scanf("%d",&m);
 7     while(m--){
 8         int n;
 9         scanf("%d",&n);
10         int tmp=5;
11         int ans=0;
12         while(tmp<=n){
13             ans=ans+n/tmp;
14             tmp=tmp*5;
15         }
16         printf("%d
",ans);
17     }
18     return 0;
19 }

nefu 118

例题nefu119，计算C(2n,n)被素数p整除多少次。（先把组合数公式写出来，然后和上题类似，分子分母分别计算，然后相减）

还有梅森素数没写，等等~