题解 | #素数的个数#
素数的个数
https://ac.nowcoder.com/acm/problem/235228
首先,筛法一定不行,数组会爆掉
筛法+前缀和版本可以去看洛谷P1865
那么本题要怎么做?
答案:MR素性判断
MR算法可以在k*(logn)^2时间复杂度内判断一个数是不是质数
只需要在l到r区间的i进行MR判断就行了
第一次写题解,而且MR算法需要很多前置知识
本题解可能不适合一点没学的人
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N= +9;
#define T int tcishu=1;cin>>tcishu;while(tcishu--)solve();
int mul(int a, int b, const int mod){
int d =a*(long double)b/mod;
int ret =a*b-d*mod;
if(ret < 0)
ret +=mod;
if(ret >= mod)
ret -=mod;
return ret;
}
int Pow(int x, int k, const int mod){
int ret =1;
for(; k; x =mul(x, x, mod), k >>=1) if(k&1) ret =mul(ret, x, mod);
return ret;
}
mt19937 engine;
bool mr(int p){
if(p < 2) return 0;
if(p == 2) return 1;
if(p == 3) return 1;
uniform_int_distribution<int> Rand(2, p-2);
int d =p-1, r =0;
while(!(d&1)) ++r, d >>=1;
for(int k =0; k < 10; ++k){
int a =Rand(engine);
int x =Pow(a, d, p);
if(x == 1 || x == p-1) continue;
for(int i =0; i < r-1; ++i){
x =mul(x, x, p);
if(x == p-1) break;
}
if(x != p-1) return 0;
}
return 1;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
srand(time(0));
int l,r;
cin>>l>>r;
int ans=0;
for(int i=l;i<=r;i++){
if(mr(i))ans++;
}
cout<<ans<<endl;
}
