fork(6) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 33000
  4. bool p[MAX];
  5. // find prime number upto 33000, we don't need above 33000 because limit of case is 10^7, and 10^7 root is around 32000
  6. void sieve(){
  7. memset(p,0,sizeof(p));
  8. p[0]=1;
  9. p[1]=1;
  10. for(int i=2;i<=MAX;i++){
  11. if(!p[i]){
  12. for(int j=i*i;j<=MAX;j+=i)
  13. p[j]=1;
  14. }
  15. }
  16. }
  17.  
  18. //find the number of exponent of a prime number if factor is of form a^x * b^y * c^z..., where a,b,c is prime
  19. // It calculates (x+1)*(y+1)*(z+1), The formula I stated in codechef to find number of factor of a number
  20. int process(int n){
  21. int ex=1;
  22. long long ans=1;
  23. if(!(n%2)){
  24. while(!(n%2)){
  25. n/=2;
  26. ex++;
  27. }
  28. }
  29. ans=ans*(ex);
  30. for(int i=3;i*i<=n;i+=2){
  31. if(!p[i] && !(n%i)){
  32. ex=1;
  33. while(!(n%i)){
  34. n/=i;
  35. ex++;
  36. }
  37. ans*=(ex);
  38. }
  39. }
  40. if(n>1) ans*=2;
  41. return ans;
  42. }
  43. // This function checks if number is of power 2, if a number is of power 2 it is of form 10,100,1000,100000 in binary
  44. // that it it will have at most 1 bit as 1 rest will be 0, K&1 checks if a bit is 1 or 0
  45. // if bit is 1 it increments cnt;
  46. // if cnt ==1 , number is of form 10,100,1000,10000 etc etc
  47. // k>>=1 is equivalent to k/2, right shifting the number 10000>>1 will become 1000
  48. bool powerof2(int k){
  49. int cnt=0;
  50. while(k>0){
  51. if(k&1) cnt++;
  52. k>>=1;
  53. }
  54. return cnt==1?1:0;
  55. }
  56. int main() {
  57. // your code goes here
  58. sieve();
  59. int t;
  60. cin>>t;
  61. while(t--){
  62. int n;
  63. cin>>n;
  64. int ans=process(n);
  65.  
  66. if(powerof2(ans))
  67. cout<<ans<<endl;
  68. else{
  69. bool fl=0;
  70. ans=1;
  71. for(int i=2;i*i<=n;i++){
  72. if(n%i==0){
  73. // if i divides n then n/i is also a factor
  74. // therefore we count factors of n/i and i, if n/i has factors of power 2 we output it
  75. // but in case of i we cannot output as such because if the number is 40, its factors will be (2,20)
  76. // (4,10), (5,8), etc etc
  77. // so we cannot output i as such so we save values of i, until the loop exits, when loop exits we have max of i stored as ans
  78. // which has number of factors of power 2
  79. int a1=process(n/i);
  80. int a2=process(i);
  81. if(powerof2(a1)){
  82. cout<<a1<<endl;
  83. cout<<n/i<<endl;
  84. fl=1;
  85. break;
  86. }
  87. else if(powerof2(a2))
  88. ans=max(ans,a2);
  89. }
  90. }
  91. if(!fl)
  92. cout<<ans<<endl;
  93. }
  94. }
  95. return 0;
  96. }
Success #stdin #stdout 0s 16096KB
stdin
3
17
48
60
stdout
2
8
24
8
30