我们首先看这样一个很简单的问题: 判定正整数 \(n\)是正整数
最简单的做法就是枚举 \(1\)到 \(n\)的所有数看是否有数是 \(n\)的因数, 时间复杂度 \(O(n)\)
稍微优化一下发现只要枚举 \(2\)到 \(\sqrt{n}\)中的数就可以了
然后发现数据范围 \(n\leq 10^{18}\), 期望执行次数直接就死掉了 QAQ
我们就要考虑新的方法了
首先引入两个定理
1, 费马小定理
如果 \(p\)是素数, 且 \(gcd(a,b)=1\), 那么 \(a^{p-1}\equiv 1(mod \ n)\)
证明什么的你随便找本数论书自己翻一下
注意它的逆定理不一定成立
2, 二次探测定理(其实这也没有一个准确的名字)
如果 \(p\)是奇素数,\(x<p\), 且 \(x^2\equiv1(mod\ p)\), 那么 \(x=1\)或 \(xp=-1\)
证明: 由同余式知 \(x^2-1\equiv0(mod\ p)\), 即 \(p|(x+1)(x-1)\)
? 又由 \(p\)是素数知 \(p|x-1\)或 \(p|x+1\), 解得 \(x=1\)或 \(x=p-1\)
诶等等 zzr 没事给证明干嘛? zzr 不是最讨厌证明了吗
由上面很简单的证明过程我们可以发现,\(x=1\)和 \(x=p-1\)这两个解其实是对所有的 \(p\)都成立的
即无论 \(p\)取什么值 \(x\)取上面两个值是一定可以的
但是当 \(p\)是一个合数的时候, 此时原同余方程的解 \(x\)就不只上面这两个了, 而是会有多个
换一句话说: 如果上面的 \(x\)取到了 1 和 \(p-1\)以外的数, 就说明 \(p\)不是一个素数了
我们主要利用上面两个性质来进行素数判定
1, 取 \(2^q*m=n-1\)(\(q,m\)均为正整数且 \(m\)为奇数), 同时任意取小于 \(n\)的正整数 \(a\)
2, 求出 \(a^{n-1}\text%n\), 如果这个值不为 1 那么 \(n\)一定是合数(利用费马小定理)
3, 遍历 \(i\), 使得 \(1\leq i \leq q\), 如果 \(2^i*m\text%n=1\)并且 \(a^{i-1}*m\text%n!=1 或 n-1\), 那么由二次探测定理就知道原同余方程出现一个特殊解, 说明 \(n\)不是一个素数
上面的方法有一个小问题: 由于费马小定理的逆定理不一定成立 (在大多数情况下成立), 因此有时我们会对 \(n\) 进行误判, 具体的, 每做一次发生误判的概率是 \(\frac{1}{4}\)
解决的方法在上面的解法中也有体现: 换用不同的 \(a\), 多进行几次即可
好了上面就是完整的 miller-rabin 测试了
一道例题: poj3518Prime Gap http://poj.org/problem?id=3518
题意: 两个相邻的素数的差值叫做 Prime Gap. 输入一个 K, 求 K 两端的素数之差, 如果 K 本身是一个素数, 输出 0;
分析: 其实数据很小你直接筛一下也可以
? 或者你直接暴力寻找当前这个数相邻的数是否是质数, 两端分别记录第一次找到的质数即可
- #include<iostream>
- #include<string.h>
- #include<string>
- #include<stdio.h>
- #include<stdlib.h>
- #include<algorithm>
- #include<vector>
- #include<queue>
- #include<map>
- using namespace std;
- #define int long long
- int n;
- int read()
- {
- int x=0,f=1;char ch=getchar();
- while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
- while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
- return x*f;
- }
- int mul(int x,int y,int n)
- {
- x%=n;y%=n;
- int ans=0,sum=x;
- while (y)
- {
- int tmp=y%2;y/=2;
- if (tmp) ans=(ans+sum)%n;
- sum=(sum+sum)%n;
- }
- return ans;
- }
- int qpow(int x,int y,int n)
- {
- int ans=1,sum=x;
- while (y)
- {
- int tmp=y%2;y/=2;
- if (tmp) ans=mul(ans,sum,n);
- sum=mul(sum,sum,n);
- }
- return ans;
- }
- bool prime(int m,int q,int a,int n)
- {
- int now=qpow(a,m,n);
- if ((now==1) || (now==n-1)) return 1;
- int i;
- for (i=1;i<=q;i++)
- {
- int x=mul(now,now,n);
- if ((x==1) && (now!=1) && (now!=n-1)) return 0;
- now=x;
- }
- if (now!=1) return 0;// 其实这里是将费马小定理的检测放在了最后, 省去再做一次快速幂
- return 1;
- }
- bool miller_rabin(int x)
- {
- if (x==2) return 1;
- if ((x<2) || (x%2==0)) return 0;
- int num=x-1,tim=0;
- while ((num) && (num%2==0)) {num/=2;tim++;}
- //cout << num << " " <<tim << endl;
- int i;
- for (i=1;i<=10;i++)// 一般都会进行 20 次左右, 不过数据范围小对吧 2333
- {
- int a=rand()%(x-1)+1;
- if (!prime(num,tim,a,x)) return 0;
- }
- return 1;
- }
- void work()
- {
- if (miller_rabin(n)) {printf("0\n");return;}
- //cout <<1;
- int l=n-1,r=n+1;
- while (!miller_rabin(l)) l--;
- while (!miller_rabin(r)) r++;
- printf("%d\n",r-l);
- }
- signed main()
- {
- n=read();
- while (n)
- {
- work();
- n=read();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2851270.html