?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
99659754 |
Practice: Priyanshu14_ |
1423K - 11 | GNU C++11 | Accepted | 889 ms | 3916 KB | 2020-11-26 19:34:15 | 2020-11-26 19:34:15 |
#include<bits/stdc++.h> using namespace std; #define Fio \ ios_base::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr) ////////// Template structure for debugging #define tr(...) trace(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void trace(const char* name, Arg1&& arg1){ cout << name << " : " << arg1 << endl; } template <typename Arg1, typename... Args> void trace(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cout.write(names, comma-names) << " : " << arg1 << " | " ; trace(comma+1, args...); } #define print(...) pr(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void pr(const char* name, Arg1&& arg1){ cout << arg1 << endl; } template <typename Arg1, typename... Args> void pr(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cout << arg1 << " "; pr(comma+1, args...); } void printV(vector<int> &arr) { cout << "Vector : "; for(int i=0;i<arr.size();i++) cout << arr[i] << " \n"[ i == arr.size()-1 ]; } void printA(int arr[], int n) { cout << "Array : "; for(int i=0;i<n;i++) cout << arr[i] << " \n"[ i == n-1 ]; } //----------- prime factorization of a number N //vector<int> factorize(int N){ //for(ll i=2; i*i <=N; i++){ //if(N % i)continue; //factors.push_back(i); //while(N % i == 0)N /= i; //} //if(N > 1)factors.push_back(q1); //return factors //} //-----------power for a ^ b //int power(int a, int b){ //int ans = 1; //while(b){ //if(b&a)ans *= a; //a *= a; //b >>= 1; //} //return ans //} //-----------factorial of a number n //int fact(int n){ //int ans = 1; //for(int i=1; i<=n; i++)ans = 1ll * ans * i % MOD; //return ans; //} //-----------N C r //int ncr(int n, int r){ //if(r > n)return 0; //if(r==0 || n==0)return 1; //if(r==1)return n; //int a = fact(n), b = 1ll * fact(n-r) % MOD, c = 1ll * fact(r) % MOD; //int ans = 1ll * a * power(b, MOD-2) % MOD; //ans = 1ll * ans * power(c, MOD-2) % MOD; //return ans; //} //------------------sieve of eratosthenes // //arr[0] = 1; //arr[1] = 1; //for(int i=2; i*i <= N; i++){ //if(!arr[i]){ //for(int j=i*i; j<=N; j++) //arr[j] = 1; //} //} #define ll long long int; const int N = 1e6+1; int arr[N]; int main(){ Fio; for(int i=0; i<=N; i++)arr[i] = 1; arr[0] = 0; arr[1] = 0; for(int i=2; i*i <= N; i++){ if(arr[i]){ for(int j=i*i; j<=N; j+=i) arr[j] = 0; } } for(int i=3; i<=N; i++)arr[i] += arr[i-1]; int t; cin >> t; while(t--){ int num; cin >> num; int sq = sqrt(num); //tr(arr[num], arr[sq],N, num, sq); cout << arr[num] - arr[sq] + 1 << "\n"; } }
?
?
?
?