AcWing 3701. 非素数个数
原题链接
简单
作者:
yxc的小迷妹
,
2023-07-17 08:30:12
,
所有人可见
,
阅读 533
#include <iostream>
using namespace std;
const int N = 1e7 + 10;
int prime[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i]) prime[cnt ++] = i;
for (int j = 0; prime[j] <= n / i; j ++)
{
st[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main()
{
get_primes(N);
int a, b;
while (cin >> a >> b)
{
a --;
int x = b > 1 ? lower_bound(prime, prime + cnt, b) - prime + 1 : 0;
x -= b != *lower_bound(prime, prime + cnt, b);
int y = a > 1 ? lower_bound(prime, prime + cnt, a) - prime + 1 : 0;
y -= a != *lower_bound(prime, prime + cnt, a);
cout << b - a - (x - y) << '\n';
}
return 0;
}