https://blog.csdn.net/ltyqljhwcm/article/details/53045840
计算小于n的所有素数：时间复杂度
#include<bits/stdc++.h>
using namespace std;
#define N 1001
bool p[N]={0};
// 注意，如果是a[100]={0}是所有的值为0,而a[100]={1}则是只有第一个值为1；
// 为了初始化方便，false为素数，true为非素数
// 算法复杂度 O(nloglogn)
int pNum=0;
bool is_prime(int a){
if(a==1){
return false;
}
//long long sqr=(long long)sqrt(1.0*a);
for(int i=2;i*i<=a;i++){
if(a%i==0){
return false;
}
}
return true;
}
// 利用小于它的素数计算是否成立，用于求解小于n的所有素数
void find_prime(int max){
int i=0,j=0;
p[0]=p[1]=true;
for(i=2;i<=max;i++){
if(p[i]==false){
if(is_prime(i)){
// 对所有与该素数成整数倍关系的标记为true（非素）
for(j=i+i;j<=max;j+=j){
p[j]=true;
}
}
else{
p[i]=true;
}
}
}
}
int main(){
int a=13,i;
find_prime(a);
for(i=0;i<a+1;i++){
printf("%d: %d\n",i,p[i]);
}
}
利用空间换时间的基于素数表的素数计算：
#include<bits/stdc++.h>
using namespace std;
#define N 1001
bool p[N]={false};
// 10^5以内可以接受。算法复杂度 nlog(n)
bool is_prime(int a){
if(a==1){
return false;
}
//long long sqr=(long long)sqrt(1.0*a);
for(int i=2;i*i<=a;i++){
if(a%i==0){
return false;
}
}
return true;
}
void find_prime(int max){
int i=0;
for(i=2;i<=max;i++){
if(is_prime(i)){
p[i]=true;
}
}
}
int main(){
int a=13,i;
find_prime(a);
for(i=0;i<a+1;i++){
printf("%d: %d\n",i,p[i]);
}
}
以上都是常规算法，下面是最快的算法（又回到了被数论统治的年代...）：
Miller_Rabin（米勒-拉宾）素数判别法：时间复杂度log2(n)
费马小定理：设p 是素数，a与p互素，则 .
这个定理反过来用，p 几乎（有非常小的概率不是，原因如下）一定是素数。
如果一个数不满足费马小定理，那么这个数必定是合数，但是如果这个数满足我们就没有办法确定是不是合数还是素数了，因为历史上有一种非常神秘的数的存在——卡密歇尔数，这类数我们也叫伪素数。无论我们选择多少个素数a，都无法排除Carmichael Number。
证明：
- 前引：p是素数，且
（0<x<p），则x=1/p-1，因为
，那么x-1等于0（x+1肯定非0）或者x+1等于p（x-1肯定非p），即
或者
。
所以且
，且
的话，p肯定不是素数。
先判断是否是奇数，偶数直接挂。
因为n是奇数，所以，必然r=n-1肯定可以分为
=
,相当于把
拆成
因为当
才行,因为此时
,能继续分拆为
但是
不行因为
没法拆成
- 若n是奇合数，则在区间0<b<n 中，最多有25%的数b ，能使n是以b为基的强伪素数。
核心部分的伪代码:
// 检测num是否是素数
for(i=0;i<20;i++){
c=num-1;
// 生成20个大于等于2小于num的随机数，从而保证错误率低于(1/4)^20
long long r=rand()%(num-2)+2;
long long y=aPowb(r,c,num);
if(y!=1){
return 404;
// 首先得保证a^(num-1)%num==1
}
for(j=0;j<k;j++){
// k是上面式子中a*2^r中的r
c/=2;
// 每次检测幂次方都折半
y=aPowb(r,c,num);
// cout<<r<<" "<<c<<" "<<num<<" "<<y<<endl;
if(y==1){
// 正常
}
else if(y==num-1){
break;
// 没有比较的必要了
}
else{
return 404;
// 肯定不是素数
}
}
}
代码：需要结合我的快速幂
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
#include<cstdlib>
#include <unordered_map>
using namespace std;
typedef long long LL;
LL aPowb(long long a,long long p,long long b){
if(p==0){
return 1;
}
if(p&1){
// 奇数
long long g=aPowb(a,p/2,b);
return ((a*g%b)*g)%b;
}
else{
long long g=aPowb(a,p/2,b);
return (g*g)%b;
}
}
bool prime(int num){
if(num&1!=1||num==1){
return false;
}
if(num==2){
return true;
}
int k=0,i=0,j=0;
int c=num-1;
while((c&1)==0){
c>>=1;
k++;
// k记录a*2^k中k的次数
}
for(i=0;i<20;i++){
c=num-1;
// 20次随机数保证客观
long long r=rand()%(num-2)+2;
long long y=aPowb(r,c,num);
if(y!=1){
return false;
}
// cout<<r<<" "<<c<<" "<<num<<" "<<y<<endl;
j=k;
while(j>0){
j--;
c/=2;
y=aPowb(r,c,num);
// cout<<r<<" "<<c<<" "<<num<<" "<<y<<endl;
if(y==1){
}
else if(y==num-1){
break;
}
else{
return false;
}
}
}
return true;
}
int main(){
int input;
cin>>input;
cout<<prime(input);
}
