Niloy007

PTRI2 - primes triangle (I) || TLE

May 16th, 2020
98
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define max 10000002
  3. #define maxN 1000000
  4. #define mod 10000000 + 5
  5. #define pb push_back
  6. #define pairs pair<int, int>
  7. #define vi vector<int>
  8. #define vb vector<bool>
  9. #define vii vector<pairs>
  10. #define lb lower_bound
  11. #define ub upper_bound
  12. #define lli long long int
  13. #define __test int tt; int Case=0; cin >> tt; while(tt--)
  14. #define endl '\n'
  15. using namespace std;
  16.  
  17. bool isPrime[max];
  18. vi Primes;
  19.  
  20. bool getPrime(int n) {
  21.   if (n < 2) return false;
  22.   if (n == 2) return true;
  23.   if (n % 2 == 0) return false;
  24.   return isPrime[n] == true;
  25. }
  26.  
  27.  
  28. void sieve() {
  29.     for (int i = 0; i <= max; i++) {
  30.         isPrime[i] = true;
  31.         // Primes.push_back(0);
  32.     }
  33.  
  34.     for (int i = 3; i * i <= max; i += 2) {
  35.         if (isPrime[i]) {
  36.             for (int j = i * i; j <= max; j += i)
  37.                 isPrime[j] = false;
  38.         }
  39.     }
  40.     Primes.push_back(2);
  41.     for (int i = 3; i < max; i += 2) {
  42.         if(isPrime[i]) {
  43.             Primes.push_back(i);
  44.         }
  45.     }
  46. }
  47.  
  48. int main() {
  49. #ifdef Niloy
  50.     freopen("input.txt", "r", stdin);
  51.     freopen("output.txt", "w", stdout);
  52. #endif
  53.     sieve();
  54.  
  55.     __test {
  56.         int a = 0, b = 0, n, check = 0;
  57.         cin >> n;
  58.         if(getPrime(n)) {
  59.             for (int i = 0; i < max; i++) {
  60.                 for (int j = 0; j <= i; j++) {
  61.                     if(Primes[a] == n) {
  62.                         cout << b + 1 << " " << j + 1 << endl;
  63.                         check = 1;
  64.                         break;
  65.                     }
  66.                     a++;
  67.                 }
  68.                 b++;
  69.  
  70.                 if(check) {
  71.                     break;
  72.                 }
  73.             }
  74.         } else {
  75.             cout << -1 << endl;
  76.         }
  77.     }
  78.  
  79.         return 0;
  80. }
RAW Paste Data