Ý tưởng của mình
gọi i là nằm trong khoản [l,r]
vì i luôn cấu tạo từ những số nguyên tố nên i^x cũng được cấu tạo từ những số nguyên tố. Thế nên ta đi đếm sao cho i^x <= r. Ta đếm những phần tử lại với nhau (gọi là cnt) rồi cập nhật res += cnt*(cnt-1)/2
(không biết code đúng hay sai nha)
#include <bits/stdc++.h>
using namespace std;
int main(){
int l,r;
cin >> l >> r;
int res=0;
long long tmp;
int cnt;
bool mark[1000001];
fill(mark+1, mark+r+1, false);
for (int i=l; i*i<= r;i++) {
if (i == 1 || mark[i]) continue;
// cout << i << ' ';
tmp = i;
cnt = 1;
while (tmp*i <= r) {
tmp*=i;
// cout << tmp << ' ';
mark[tmp] = true;
cnt++;
}
// cout << endl;
res += cnt * (cnt-1)/2;
}
cout << res;
return 0;
}