Advertisement
LEGEND2004

D

Jan 31st, 2023
854
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  5. #define pb emplace_back
  6. const int MAXX = 1e4 + 5;
  7. const int N = 1e4;
  8. const int NUM = 4000000;
  9.  
  10. int t , n , i , j , k , s , m , cnt;
  11. bool p[MAXX];
  12. int ans[MAXX];
  13. vector<int> v;
  14.  
  15. void sieve(){
  16.     p[2] = true;
  17.     for(i = 3; i < N; i += 2){
  18.         p[i] = true;
  19.     }
  20.     for(i = 3; (i * i) < N; i += 2){
  21.         if(p[i]){
  22.             for(j = (i + i + i); j < N; j += (i + i))
  23.                 p[j] = false;
  24.         }
  25.     }
  26.     v.pb(2);
  27.     for(i = 3; i < N; i += 2){
  28.         if(p[i])
  29.             v.pb(i);
  30.     }
  31. }
  32.  
  33. signed main()
  34. {
  35.     _FastIO;
  36.     sieve();
  37.     for(i = 1; i <= NUM; i++){
  38.         k = i;
  39.         s = 1;
  40.         for(j = 0; (v[j] * v[j]) <= k; j++){
  41.             if(k % v[j])
  42.                 continue;
  43.             cnt = 0;
  44.             while(k % v[j] == 0){
  45.                 k /= v[j];
  46.                 cnt++;
  47.             }
  48.             s *= (cnt + 1);
  49.         }
  50.         if(k > 1)
  51.             s *= 2;
  52.         while(m < s){
  53.             m++;
  54.             ans[m] = i;
  55.         }
  56.     }
  57.     scanf("%d" , &t);
  58.     while(t--){
  59.         scanf("%d" , &n);
  60.         printf("%d" , ans[n]);
  61.         putchar('\n');
  62.     }
  63.     return 0;
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement