Niloy007

HS08PAUL - A conjecture of Paul Erdős

Apr 13th, 2021
717
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define Niloy
  3. #define int int64_t
  4. #define MAX (int) 1e7 + 123
  5. #define MOD 1e9
  6. #define pb push_back
  7. #define pairs pair<int, int>
  8. #define vi vector<int>
  9. #define vb vector<bool>
  10. #define vii vector<pairs>
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define endl '\n'
  14. #define llu unsigned long long
  15. using namespace std;
  16. /* ----------------------------------------------------------------------------------- */
  17. #define scan(a)           scanf("%lld", &a);
  18. #define rep(i, a, n) for (int i = a; i < n; i++)
  19. #define REP(i, a, n) for (int i = a; i <= n; i++)
  20.  
  21. /* ----------------------------------------------------------------------------------- */
  22.  
  23. bitset<MAX> isPrime;
  24. vi Prime;
  25. int ans[MAX];
  26.  
  27. void primeGen(int n) {
  28.     for (int i = 3; i <= n; i += 2) {
  29.         isPrime[i] = 1;
  30.     }
  31.     isPrime[2] = 1;
  32.     int sq = sqrt(n);
  33.  
  34.     for (int i = 3; i <= sq; i += 2) {
  35.         if (isPrime[i]) {
  36.             for (int j = i * i; j <= n; j += (i * 2)) {
  37.                 isPrime[j] = 0;
  38.             }
  39.         }
  40.     }
  41.  
  42.     Prime.pb(2);
  43.     for (int i = 3; i <= n; i += 2) {
  44.         if (isPrime[i]) {
  45.             Prime.pb(i);
  46.         }
  47.     }
  48. }
  49.  
  50. void solve() {
  51.     int lim = 1e7;
  52.     primeGen(lim);
  53.     REP(x, 1, 3200) {
  54.         REP(y, 1, 60) {
  55.             int d = (x * x) + (y * y * y * y);
  56.             if (d > lim) {
  57.                 continue;
  58.             }
  59.             if (isPrime[d]) {
  60.                 ans[d] = 1;
  61.             }
  62.         }
  63.     }
  64.     REP(i, 1, lim) {
  65.         ans[i] += ans[i - 1];
  66.     }
  67.     int t;
  68.     scan(t);
  69.     while (t--) {
  70.         int a;
  71.         scan(a);
  72.         cout << ans[a] << endl;
  73.     }
  74. }
  75.  
  76. int32_t main() {
  77.     // input();
  78.     // fastInput;
  79.     solve();
  80.  
  81.     // __test {
  82.     //  solve();
  83.     // }
  84.  
  85.     // showTime;
  86.     return 0;
  87. }
  88.  
RAW Paste Data