1234567891011121314151617181920212223242526272829303132 |
- //
- // Created by jal on 2019-05-01.
- //
- #include<bits/stdc++.h>
- using namespace std;
- int main(){
- int l,r;
- cin >> l >> r;
- int n = r - l + 1;
- vector<bool>a(n, true);
- vector<int>prime;
- int m = sqrt(r);
- vector<bool>f(m+1, true);
- for(int i = 2; i <= m; i++){
- if(f[i]){
- prime.push_back(i);
- }
- for(int j = 0; j < prime.size() && prime[j]*i <= m; j++){
- f[prime[j]*i] = false;
- }
- }
- for(int i = 0; i < prime.size(); i ++){
- int k = prime[i];
- for(int j = max(2, (l + k - 1) / k * k); j <= r; j+= k){
- a[j-l] = false;
- }
- }
- cout << accumulate(a.begin(), a.end(), 0) << endl;
- }
- //2100000000 2101000000
|