集训营团队题目 输出素数个数4题解
2024-07-28 09:17:06
发布于：湖南
27阅读
0回复
0点赞
好消息，我发题了！链接（在团队里，团队外打不开）
first，我要令 .
首先我们看到数据范围这么大，用普通的判断质数肯定是行不通的
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
bool check(int n){
if(n == 2) return 1;
if(n < 2 || n % 2 == 0) return 0;
for(int i = 3; i * i <= n; i += 2){
if(n % i == 0) return 0;
}
return 1;
}
int main(){
int l, r, ct = 0;
scanf("%d%d", &l, &r);
for(int i = l; i <= r; i++){
ct += check(i);
}
cout << ct;
return 0;
}
时间复杂度：，放在这个的数据直接被硬控 秒.
但是用筛的话， 任何线性筛都会爆炸
这时候，不得不放出我的筛法了（
算了还是不展示了（
正经点，我们可以改进埃式筛
普通埃式筛是筛掉 以内所有的数，但现在我们只要范围内的数就行了，所以我们可以转找范围内的数筛
#include <iostream>
#include <iostream>
#include <cstdio>
#include <bitset>
#define int long long
using namespace std;
bool vis[1000005];
signed main(){
int l, r, ct = 0;
cin >> l >> r;
if(l == 1) l++;//要是是1会多判一个，所以要改成2
for(int i = 2; i <= 48000; i++){//筛到根号r就行了
int low = (l - 1) / i * i + i;//找出第一个在范围内的i的倍数
if(low == i) low += i;//i不能算
for(; low <= r; low += i){//开筛！
vis[low - l] = 1;
}
}
for(int i = 0; i <= r - l; i++){
ct += vis[i];
}
cout << r - l + 1 - ct;
return 0;
}
时间复杂度：（蒙的）.
这个已经可以过了，但是还能不能再快点呢？
#include <iostream>
#include <cstdio>
#include <bitset>
#include <vector>
#define int long long
using namespace std;
bool vis[1000005];
vector <int> v;
signed main(){
for(int i = 2; i <= 48000; i++){//多筛一次，只挑质数，加速
if(!vis[i]){
v.push_back(i);
for(int j = i << 1; j <= 48000; j += i) vis[j] = 1;
}
else vis[i] = 0;
}
int l, r, ct = 0;
cin >> l >> r;
if(l == 1) l++;
for(auto i:v){
int low = (l - 1) / i * i + i;
if(low == i) low += i;
for(; low <= r; low += i){
vis[low - l] = 1;
}
}
for(int i = 0; i <= r - l; i++){
ct += vis[i];
}
cout << r - l + 1 - ct;
return 0;
}
时间复杂度：（也是蒙的）.
反正更快就行了
有帮助，赞一个