题目：
A. 天天写作业
Problem ID: 1303
Contest ID: 5885
必做题
Memory Limit Exceeded
60 分
Time Limit:
1000ms
Memory Limit:
65536kB
题目描述
暑假作业好多…天天写的头都大了，数学题里有一题，题目很简单，可是把天天纠结了很久了。。。计算从[A,B](闭区间包括A和B, A <= B, 且0<=B <= 1000000000, B - A <= 100000)之间，一共有多少素数？（不要交表！程序不能大于3KB。。。）
输入格式
一行，两个整数，用空格分开，分别是A和B。
输出格式
一行，代表[A,B]之间有多少素数。
样例
Input 1
3 10
Output 1
3
数据范围
A <= B, 且0<=B <= 1000000000, B - A <= 100000
蒟蒻用了两种方法
都是MLE60
1.线性筛:
#include<bits/stdc++.h>
using namespace std;
bool vis[1000000001]={false};
int primes[114514];
int cnt=0,ans=0;
void get_primes(int a,int b){
for(int i=2;i<=b;i++){
if(!vis[i]){
primes[cnt++]=i;
if(i>=a) ans++;
}
for(int j=0;primes[j]*i<=b;j++){
vis[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int main(){
int a,b;
cin>>a>>b;
get_primes(a,b);
cout<<ans;
return 0;
}
2.埃式筛法
#include<bits/stdc++.h>
using namespace std;
bool vis[1000000001]={false};
int ans=0;
void get_primes(int a,int b){
for(int i=2;i<=b;i++){
if(vis[i] ) continue;
else{
ans+=(i>=a)?1:0;
for(int j=2*i;j<=b;j+=i){
vis[j]=true;
}
}
}
}
int main(){
int a,b;
cin>>a>>b;
get_primes(a,b);
cout<<ans;
return 0;
}
有没有大佬看一下是什么原因
