素数与Miller-Rabin测试
素数及其性质
素数又称质数。指整数在一个大于 111 的自然数中,除了 111 和此整数自身外,没法被其他自然数整除的数。
性质1 有无穷多个素数。
证明: 用反证法。设已知的最大素数为 PPP,考虑S=2×3×5×…×P+1S=2\times3\times5\times…\times P+1S=2×3×5×…×P+1
显然所有已知素数都无法整除 SSS,所以我们找到了一个更大的素数。Q.E.D..\text{Q.E.D..}Q.E.D..
性质2 对于正整数 p,qp,qp,q,若 ppp 是素数且 p∤qp\nmid qp∤q,则 p,qp,qp,q 互素。
证明: 由素数定义知, ppp 的因子为 1,p1,p1,p。
∵p∤q,\because p\nmid q,∵p∤q,
∴gcd(p,q)=1,\therefore \gcd(p,q)=1,∴gcd(p,q)=1,
即 p,qp,qp,q 互素。Q.E.D..\text{Q.E.D..}Q.E.D..
性质3 对于任意正整数 NNN,存在连续的 NNN 个合数。
证明: 考虑
(N+1)!+2,(N+1)!+3,(N+1)!+4,...,(N+1)!+N(N+1)!+2,(N+1)!+3,(N+1)!+4,...,(N+1)!+N(N+1)!+2,(N+1)!+3,(N+1)!+4,...,(N+1)!+N
这 NNN 个数都是合数。Q.E.D..\text{Q.E.D..}Q.E.D..
性质4 若 ppp 是素数,aaa 是小于 ppp 的正整数,则 apmod  p=1a^p\mod p= 1apmodp=1。
证明: 详细证明戳这里。
题目描述 loj10197\text{loj10197}loj10197
给定两个整数 L,RL,RL,R,求闭区间 [L,R][L,R][L,R] 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时,输出靠前的素数对。
输入格式
多组数据。每行两个数 L,RL,RL,R。
输出格式
详见输出样例。
样例输入
2 17
14 17
样例输出
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
数据范围与提示
对于全部数据,1≤L≤R≤2311≤L≤R≤2^{31}1≤L≤R≤231,R−L≤106R-L≤10^6R−L≤106。
Solution 10197\text{Solution 10197}Solution 10197
由于 R−LR-LR−L 的数值较小,自然想到把 [L,R][L,R][L,R] 间的素数筛出,然后找出答案。
对于 [L,R][L,R][L,R] 区间的数的质因子集 {S}\{S\}{S},必有
∣S∣≤maxR≈5×104|S|≤\sqrt{\max R}≈5\times10^4∣S∣≤maxR≈5×104先筛出 5×1045\times10^45×104 内的素数,再尝试从 SSS 的 ⌈LS⌉\lceil \frac{L}{S} \rceil⌈SL⌉ 倍开始筛去合数,剩下的就是素数。注意特判 111。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define reg register
typedef long long ll;
const int inf=1e6+10;
int L,R;
int a[1000010],b[1000010],d[1000010];
int len=0,c,set=0;
int l1,r1,l2,r2,ans1,ans2;
void work(){
memset(b,1,sizeof(b));
for(reg int i=2;i<=inf;++i){
if(b[i]){
b[i]=0;a[++len]=i;
for(reg int j=i+i;j<=inf;j+=i)
b[j]=0;
}
}
}
int main(){
work();
while(scanf("%d%d",&L,&R)!=EOF){
l1=r1=l2=r2=0;ans1=0x3f3f3f3f;ans2=-1;
memset(d,1,sizeof(d));
if(L==1) d[0]=0;
for(reg int i=1;i<=len;++i){
c=L/a[i];
//if(ll(a[i]*c)<(ll)L) ++c;
for(reg int j=c<=1?2:c;j<=R/a[i];++j){
int dd=j*a[i]-L;
if(dd>R-L||dd<0) continue;
d[dd]=0;
}
}
for(reg int i=0;i<=R-L;++i)
if(d[i]){
set=i;
break;
}
if(set==-1){
puts("There are no adjacent primes.");
continue;
}
for(reg int i=set+1;i<=R-L;++i)
if(d[i]){
if(i-set<ans1){
ans1=i-set;
l1=set+L;r1=i+L;
}
if(i-set>ans2){
ans2=i-set;
l2=set+L;r2=i+L;
}
set=i;
}
// for(reg int i=0;i<=R-L;++i)
// printf("%d ",d[i]);
// puts("");
if(!l1&&!r1&&!l2&&!r2)
puts("There are no adjacent primes.");
else
printf("%d,%d are closest, %d,%d are most distant.\n",l1,r1,l2,r2);
}
}
题目描述 loj10198\text{loj10198}loj10198
原题来自:NOIP 2012 普及组
已知正整数 nnn 是两个不同的质数的乘积,试求出较大的那个质数。
输入格式
输入只有一行,包含一个正整数 nnn。
输出格式
输出只有一行,包含一个正整数 ppp,即较大的那个质数。
样例输入
21
样例输出
7
数据范围与提示
对于 30%30\%30% 的数据, n≤1000n\leq1000n≤1000;
对于全部数据,6≤n≤2×1096\leq n\leq 2\times10^96≤n≤2×109。
Solution 10198\text{Solution 10198}Solution 10198
由于 nnn 是 222 个素数之积,所以当我们找到一个较小素数 xxx 使 x∣nx|nx∣n 时,另一个素因子就是 nx\frac{n}{x}xn。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define reg register
typedef long long ll;
ll n;
bool b[200000010];
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
void work(){
memset(b,1,sizeof(b));
for(reg ll i=2;i*i<=n;++i){
if(b[i]){
b[i]=0;
if(!(n%i)){
printf("%lld",max(i,n/i));
exit(0);
}
for(reg ll j=i+i;j<=min(n,20000000);j+=i)
b[j]=0;
}
}
}
int main(){
scanf("%lld",&n);
work();
}
题目描述 loj10200\text{loj10200}loj10200
哥德巴赫猜想:任何大于 444 的偶数都可以拆成两个奇素数之和。
你的任务是:验证小于 10610^6106 的数满足哥德巴赫猜想。
输入格式
多组数据,每组数据一个 nnn。
读入以 000 结束。
输出格式
对于每组数据,输出形如 n=a+bn=a+bn=a+b,其中 a,ba,ba,b 是奇素数。若有多组满足条件的 a,ba,ba,b,输出 b−ab-ab−a 最大的一组。
若无解,输出 Goldbach's conjecture is wrong.
。
样例输入
8
20
42
0
样例输出
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
数据范围与提示
对于全部数据,6≤n≤1066\leq n\leq10^66≤n≤106。
Solution 10200\text{Solution 10200}Solution 10200
- 预处理出 1−n1-n1−n 的素数;
- 对于每一个 nnn,枚举 aaa 判断是否合法。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define reg register
int n,s;
int a[100010],b[1000010];
int len=0;
int f[1000010];
void reset(){
memset(b,1,sizeof(b));
for(reg int i=2;i*i<=1000000;++i)
if(b[i]){
a[++len]=i;
for(reg int j=i+i;j<=1000000;j+=i)
b[j]=0;
}
}
void work(int x){
if(!x) return;
if(f[x]){
printf("%d = %d + %d\n",x,f[x],x-f[x]);
return;
}
for(reg int i=2;i<=len/2+1;++i)
if(b[x-a[i]]){
f[x]=a[i];
printf("%d = %d + %d\n",x,f[x],x-f[x]);
return;
}
}
int main(){
memset(f,0,sizeof(f));
reset();
do{
scanf("%d",&s);
work(s);
}while(s);
}
题目描述 loj10201\text{loj10201}loj10201
Sherlock 有了一个新女友(这太不像他了!)。情人节到了,他想送给女友一些珠宝当做礼物。
他买了 nnn 件珠宝。第 iii 件的价值是 i+1i+1i+1。那就是说,珠宝的价值分别为 2,3,4,...,n+12,3,4,...,n+12,3,4,...,n+1。
Watson 挑战 Sherlock,让他给这些珠宝染色,使得一件珠宝的价格是另一件的质因子时,两件珠宝的颜色不同。并且,Watson 要求他最小化颜色的使用数。
请帮助 Sherlock 完成这个简单的任务。
输入格式
只有一行一个整数 nnn,表示珠宝件数。
输出格式
第一行一个整数 kkk,表示最少的染色数;
第二行 nnn 个整数,表示第 111 到第 nnn 件珠宝被染成的颜色。若有多种答案,输出任意一种。
样例输入 1
3
样例输出 1
2
1 1 2
样例输入 2
4
样例输出 2
2
2 1 1 2
样例说明
因为 222 是 444 的一个质因子,因此第一件珠宝与第三件珠宝的颜色必须不同。
数据范围与提示
对于全部数据,1≤n≤1051\leq n\leq10^51≤n≤105。
Solution 10201\text{Solution 10201}Solution 10201
易证,所有的素数都是互素的。
所以,我们可以把所有的素数全部染成一种颜色,把其他数染成另一种颜色。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define reg register
int n;
int a[100010];
void work(){
memset(a,1,sizeof(a));
for(reg int i=2;i<=n+5;++i)
if(a[i])
for(reg int j=i+i;j<=n+5;j+=i)
a[j]=0;
}
int main(){
scanf("%d",&n);
if(n==1){
puts("1\n1");
exit(0);
}
if(n==2){
puts("1\n1 1");
exit(0);
}
work();
puts("2");
for(reg int i=1;i<=n;++i)
printf("%d ",a[i+1]?1:2);
}
题目描述 luoguP1306\text{luoguP1306}luoguP1306
对于Fibonacci数列:1,1,2,3,5,8,13......1,1,2,3,5,8,13......1,1,2,3,5,8,13...... 大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第 nnn 项和第 mmm 项的最大公约数是多少?
输入格式
两个正整数 nnn 和 mmm。(n,m≤109n,m\leq10^9n,m≤109)
输出格式
fnf_nfn 和 fmf_mfm 的最大公约数。
由于看了大数字就头晕,所以只要输出最后的8位数字就可以了。
输入样例
4 7
输出样例
1
Solution P1306\text{Solution P1306}Solution P1306
今有结论gcd(fn,fm)=fgcd(n,m)\gcd(f_n,f_m)=f_{\gcd(n,m)}gcd(fn,fm)=fgcd(n,m)
证明: 当 n=mn=mn=m 时,结论显然成立。不妨设 n<mn< mn<m,记 fn=a,fn+1=bf_n=a,f_{n+1}=bfn=a,fn+1=b。
则fn+2=a+bf_{n+2}=a+bfn+2=a+bfn+3=a+2bf_{n+3}=a+2bfn+3=a+2bfn+4=2a+3bf_{n+4}=2a+3bfn+4=2a+3b.........fm=a⋅fm−n−1+b⋅fm−nf_m=a·f_{m-n-1}+b·f_{m-n}fm=a⋅fm−n−1+b⋅fm−n
而gcd(fn,fm)=gcd(fn,a⋅fm−n+1+b⋅fm−n)\gcd(f_n,f_m)=\gcd(f_n,a·f_{m-n+1}+b·f_{m-n})gcd(fn,fm)=gcd(fn,a⋅fm−n+1+b⋅fm−n)
∴gcd(fn,fm)=gcd(fn,b⋅fm−n)\therefore\gcd(f_n,f_m)=\gcd(f_n,b·f_{m-n})∴gcd(fn,fm)=gcd(fn,b⋅fm−n)。
引理:对于 ∀n∈Z∗\forall n\in\Z^*∀n∈Z∗,有 gcd(fn,fn+1)=1\gcd(f_n,f_{n+1})=1gcd(fn,fn+1)=1。
证明: gcd(fn,fn+1)=gcd(fn,fn+fn−1)=gcd(fn,fn−1)=gcd(fn−1,fn−1+fn−2)=gcd(fn−1,fn−2)…=gcd(f2,f1)=1\begin{aligned}\gcd(f_n,f_{n+1})&=\gcd(f_n,f_n+f_{n-1})\\
&=\gcd(f_n,f_{n-1})\\
&=\gcd(f_{n-1},f_{n-1}+f_{n-2})\\
&=\gcd(f_{n-1},f_{n-2})\\
&…\\
&=\gcd(f_2,f_1)\\
&=1
\end{aligned}gcd(fn,fn+1)=gcd(fn,fn+fn−1)=gcd(fn,fn−1)=gcd(fn−1,fn−1+fn−2)=gcd(fn−1,fn−2)…=gcd(f2,f1)=1
∴\therefore∴gcd(fn,fm)=gcd(fn,fm−n)=gcd(fn,fmmod  n)\begin{aligned}\gcd(f_n,f_m)&=\gcd(f_n,f_{m-n})\\
&=\gcd(f_n,f_{m\mod n})
\end{aligned}gcd(fn,fm)=gcd(fn,fm−n)=gcd(fn,fmmodn)
我们发现,这实质就是求解 gcd(m,n)\gcd(m,n)gcd(m,n) 的过程,
∴\therefore∴gcd(fn,fm)=gcd(fgcd(n,m),f0)=fgcd(n,m)\begin{aligned}\gcd(f_n,f_m)&=\gcd(f_{\gcd(n,m)},f_0)\\
&=f_{\gcd(n,m)}
\end{aligned}gcd(fn,fm)=gcd(fgcd(n,m),f0)=fgcd(n,m)
于是问题转化成求 fgcd(n,m)f_{\gcd(n,m)}fgcd(n,m) 的值。使用矩阵乘法和快速幂完成求解。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define reg register
typedef long long ll;
int a,b;
int n,m;
struct node{
ll a[3][3];
int x,y;
node(){
x=y=0;
memset(a,0,sizeof(a));
}
void pt(){
printf("%lld",a[1][2]);
}
}s,t,ans;
node T(node a,node b){
node c;c.x=a.x;c.y=b.y;
for(reg int i=1;i<=c.x;++i)
for(reg int j=1;j<=c.y;++j)
for(reg int k=1;k<=a.y;++k)
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%m;
return c;
}
node QT(node a,int b){
if(b<=1) return a;
node c=QT(a,b/2);
if(b%2)
return T(T(c,c),a);
else
return T(c,c);
}
int main(){
scanf("%d%d",&a,&b);
n=std::__gcd(a,b);m=100000000;
if(n<=2){
puts("1");
exit(0);
}
s.x=1;s.y=2;s.a[1][1]=s.a[1][2]=1;
t.x=2;t.y=2;t.a[1][1]=0;t.a[1][2]=t.a[2][1]=t.a[2][2]=1;
ans=T(s,QT(t,n-2));
ans.pt();
}
Miller-Rabin 测试
戳这儿进行预习。
Miller-Rabin 测试基于以下定理。
若 ppp 是素数,xxx 是小于 ppp 的正整数,且 x2mod  p=1x^2\mod p=1x2modp=1,则 x=1x=1x=1 或 x=p−1x=p-1x=p−1。
以 n=341n=341n=341 为例,Miller-Rabin 测试步骤如下:
- 计算得 2341−1mod  341=12^{341-1}\mod 341=12341−1mod341=1;
- 将 341341341 除以 222,得到 170170170;
- 计算得 2170−1mod  341=12^{170-1}\mod 341=12170−1mod341=1;
- 将 170170170 除以 222,得到 858585;
- 计算得 285mod  341=32≠12^{85} \mod341=32\ne1285mod341=32̸=1,所以 341341341 不是素数(341341341 是伪素数)。
- * 若是素数,则换用 333 或其他素数重复以上操作。
一般地,我们把 ∀n\forall n∀n 有 a(n−1)mod  n=1a^{(n-1)}\mod n=1a(n−1)modn=1 的合数 nnn 叫做以 aaa 为底的 伪素数。
最新文章
- CF Round #367 C题
- MFC---给按钮加上快捷键
- Linux 卸载mysql-libs包出现错误
- 大叔也说Xamarin~Android篇~环境部署与破解
- ovirt-engine安装
- C#加密解密大全
- map的用法
- (转)Tomcat的目录结构
- How Tomcat Works(七)
- linux下修改ip地址,默认网关以及DNS
- Unreal Engine 4 创建Destructible Mesh(可破坏网格)
- 解决Xcode7之后发送网络请求http格式不支持报错问题
- Codeforces 626F Group Projects(滚动数组+差分dp)
- 打印文章 FZOJ 5190
- sql语句创建数据库和表
- PTA 7-2 符号配对(栈模拟)
- c语言第一次作业--顺序、分支结构
- 那些不能遗忘的知识点回顾——C/C++系列(笔试面试高频题)
- 获取oracle当前系统设置了哪些事件
- weblogic启动错误 Unrecognized option: -jrockit