题目描述
算法1
第一次用暴力尝试了跑了一部分数的约数个数,并从中取出约数个数等于5的数
得到了下列这些数
16 81
625
2401
14641 28561 83521
130321 279841 707281 923521
1874161 2825761 3418801 4879681 7890481
12117361 13845841 13845841 20151121
......
由此可以发现,这些数每一个都是一个未知质数x的四次方
所以可以先使用筛法求得一定范围的质数并储存,再通过遍历质数表,
找到其中质数的四次方是否处于给定[l,r]区间内,
最后累加个数
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, INF = 0x3f3f3f3f ;
int cnt;
bool st[N];
int primes[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); //预处理质数
int T;
scanf("%d", &T);
while (T--) {
ll l, r;
ll cnt = 0;
scanf("%lld %lld", &l, &r);
for (auto x : primes) {
ll p = (ll)x * x * x * x;
if (l <= p && p <= r) cnt++;
if (x > r) break;//不在[l,r]区间中
}
printf("%lld\n", cnt);
}
return 0;
}