文章
117
粉丝
69
获赞
860
访问
113.7k
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int l, r;
int primes[N], cnt, s[N];
bool st[N];
void get_primes(int n)
{
for(int i = 2; i <= n; i ++)
{
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; primes[j] <= n/ i; j ++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
get_primes(N - 10);
for(int i = 1; i <= N - 10; i ++)
s[i] += s[i - 1] + st[i];
while(cin >> l >> r)
{
cout << s[r] - s[l - 1]<< endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发