Chứng minh: dả dụ số cần xét là `a`, ta gọi `b` là ước của `a`, vì thế ta luôn có một ước nữa là `a/b`. Vậy để có đúng 3 ước thì `b = a/b`
Nếu bạn là một người hay giải toán bạn sẽ dễ nhận ra là chỉ có bình phương số nguyên tố mới có khả năng làm việc trên. Thế nên ta chỉ cần tốn O(sqrt(n)) để đếm toàn bộ số nguyên tố, gọi `a` là tất cả số nguyên tố thỏa mãn `L < a^2 < R`. Như vậy ta cần đếm tất cả số `a` bằng sàng nguyên tố
Tham khảo code của
Sơn Đẹp Zai
Setup Sơn's define
// _____ _ _ // / ____| | | (_) // | (___ ___ _ __ __| | ___ _ __ ______ _ _ // \___ \ / _ \| '_ \ / _` |/ _ \ '_ \ |_ / _` | | // ____) | (_) | | | | | (_| | __/ |_) | / / (_| | | // |_____/ \___/|_| |_| \__,_|\___| .__/ /___\__,_|_| // | | // |_|#include <bits/stdc++.h> #define nmax 100005 #define oo 10000000007 #define mod 1000000007 #define reset(x) memset(x, 0, sizeof x) #define PB(x) push_back(x) #define F first #define S second #define sonin cin #define sonout cout #define debug(x) cout << "Loli -> " << #x << " : " << x << "\n" #define debugAry(x, a, b, y) for(int y = a; y<=b; y++) cout << #x << "[" << y << "]" << " -> " << x[y] << "\n" #define filename "TOWERBOX" #define fileNX freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout); #define fileN freopen(filename".inp", "r", stdin); #define fileX freopen(filename".out", "w", stdout); #define toiuuhoa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define SZ(a) (int) a.size() #define FOU(x,a,b) for (lli x=a;x<=b;x++) #define FOD(x,a,b) for (lli x=a;x>=b;x--) #define FOA(a,b) for(auto &a:b) #define ALLvec(a) a.begin(),a.end() #define REU(x,a,b) for (lli x=a;x<b;x++) #define RED(x,a,b) for (lli x=a;x>b;x--) #define AutoCinAry(a,b,x) for(int a = 1; a<=b; a++) cin >> x[i]; #define dembit1(x) __builtin_popcount(x) #define bit(x,i) ((x>>(i-1))&1ll) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1ll<<(i-1))) #define EL cout << "\n"; #define EX exit(0); #define Ary(x, i, j, a) x[(i - 1) * a + j] #define epsinon 1e-8 #define Son_onii_chan main #define times double stime = clock(); #define gettime cerr << "Time executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n"; using namespace std; typedef long long lli; typedef long double ldo; typedef double dou; typedef vector vi; typedef vector vvi; typedef pair<lli, lli> pii; typedef vector vpi; typedef deque dqll;
O(sqrt(n))
lli l, r, res;
bool check[40000];
int Son_onii_chan(){
//fileNX
toiuuhoa
sonin >> l >> r;
lli sio = sqrt(r);
res = 0;
memset(check, 0, sizeof check);
FOU(i,2,sio){
if (!check[i]) {
for (lli j = 2 * i; j = l)
res++;
}
}
sonout << res;
return 0;
}
Tổng cộng 2 trả lời