首页 > 代码库 > 【数论】素数的判定与筛法
【数论】素数的判定与筛法
素数的判定与筛法
判定：很简单嘛！暴力大法参上！
#include<iostream>#include<cmath>unsigned long int n,i,j,a,b;using namespace std;int main(){ cin>>n; j=(int)sqrt(n); for(i=2;i<=j;i++) if(n%i==0) break; if(i>j&&n!=0&&n!=1) cout<<"Yes"; else cout<<"No";}
（不相信从来不刷水的我竟然做了这样的题……）
这就是传说中的O(根号N)大暴力……
那么还有个算法叫Miller-rabin……
那么我们来介绍一下这是个什么东西：
首先让我们了解这几个概念：
费马小定理：对于素数p和任意整数a，有ap ≡ a(mod p)（同余）。反过来，满足ap ≡ a(mod p)，p也几乎一定是素数。
伪素数：如果n是一个正整数，如果存在和n互素的正整数a满足 an-1 ≡ 1(mod n)，我们说n是基于a的伪素数。如果一个数是伪素数，那么它几乎肯定是素数。
Miller-Rabin测试：不断选取不超过n-1的基b(s次)，计算是否每次都有bn-1 ≡ 1(mod n)，若每次都成立则n是素数，否则为合数。
设待测数为n，取一个比n小的正整数a,设n-1=d*2^r。若n是素数，则要么a^d mod n = 1,要么存在一个i,满足0≤i＜r且a^(d*2^i )mod n = -1
经过独立的t轮Miller-Rabin算法将一个合数误判为素数的可能性不大于 (1/4)t，(正确实现的算法不会误判素数为合 数)，这个误判概率在基于Fermat定理的算法中是最好的。一轮Miller-Rabin算法的最坏情况时间复杂度为 (1+O(1))log2(n)( 以模n乘法为基本操作)。如果以单精度乘法操作作为时间复杂度的衡量，则一轮优化的Miller-Rabin算法的最 坏情况时间复杂度为O(log32 (n) 。从时间复杂度来看Miller- Rabin算法的性能是很好的。在实际应用中，Miller-Rabin 算 法的实际执行速度也很快。
大家可以多次调用该函数，使得错误率降低。
#include<stdio.h>#include<stdlib.h>#include<cmath>bool witness(__int64 a,__int64 n){ __int64 t,d,x; d=1; int i=ceil(log(n-1.0)/log(2.0)) - 1; for(;i>=0;i--) { x=d; d=(d*d)%n; if(d==1 && x!=1 && x!=n-1) return true; if( ((n-1) & (1<<i)) > 0) d=(d*a)%n; } return d==1? false : true;}bool miller_rabin(__int64 n){ if(n==2) return true; if(n==1 || ((n&1)==0)) return false; for(int i=0;i<50;i++){ __int64 a=rand()*(n-2)/RAND_MAX +1; if(witness(a, n)) return false; } return true;}int main(){ int n,cnt; __int64 a; while(scanf("%d",&n)!=EOF) { cnt=0; while(n--) { scanf("%I64d",&a); if(miller_rabin(a)) cnt++; } printf("%d\n",cnt); } return 0;}
筛法：筛法有3种时间复杂度，详细说应该有四种，最后一种貌似是打表……
1.O(N*根号N)
2.O(NlogN)
3.O(N)
第一种方法：很明显的暴力啊……循环+判断
第二种方法：这是比较常用的一种筛法：埃氏筛（俗称垃圾筛），根本思想很简单：我们从1往N搜，假如我们遇到了一个没有被标记为不是素数的数，那么我们把它的倍数（>1）都标记为非素数……
for(int i=2;i<=1000000;i++)if(!FP[i]){ PL[++e]=i; for(long long j=(long long)i*i;j<=1000000;j+=i) FP[j]=1;}
第三种方法：线性筛，这个还是根据代码来解释吧……
第一行：应该没必要解释吧
第二行：从1到N枚举
第三行：同埃氏筛
第四行：枚举素数
第五行：如果乘上i大于n了，那么后面也肯定大于n，so break……
第六行：把prime[j]的i倍标记为不是素数
第七行：这个是代码的核心句，如果没有这句，那么它的时间复杂度与埃氏筛一样，但是我们来看一看12，它是在什么时候被枚举到的？第6次循环，也就是说，我们这次如果不加这条语句，那么有写情况是算重复了，那么这条鱼句就可以保证它不会重复。
1. 任何一个合数都可以表示成一个质数和一个数的乘积
2. 假设A是一个合数，且A = x * y，这里x也是一个合数，那么有:一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积
例如: 如果i = 8; 那么由于i%2 == 0; 因此对于i=8就只需要检查primes[1]=2即可，因为对于大于primes[1]的质数，像3，有:8*3 = 2*4*3 = 12*2
也就是说24(8*3=24)并不需要在8时检查，在12时才检查
【数论】素数的判定与筛法