Advertisement
Maruf_Hasan

NOD

May 6th, 2020
44
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.71 KB | None | 0 0
  1.  
  2. //In the Name of Allah Most Gracious, Most Merciful//
  3. /*If you want something you've never had, you have to do something you never did.*/
  4.  
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7.  
  8.  
  9. #define pb push_back
  10. #define ll long long
  11. #define pii pair<ll,ll>
  12. #define pll pair<ll,ll>
  13. #define M 10000007
  14. #define INF 1e9
  15. #define INFL 1e18
  16. #define PI acos(-1)
  17. #define mp make_pair
  18. #define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  19. //const ll fx[]= {+1,-1,+0,+0};
  20. //const ll fy[]= {+0,+0,+1,-1};
  21. //const ll fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
  22. //const ll fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
  23. //const ll fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
  24. //const ll fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
  25. #define SIZE 100100
  26.  
  27.  
  28. vector<ll>prime;
  29. bool mark[M+10];
  30. vector<ll>v;
  31.  
  32. ll arr[SIZE];
  33.  
  34.  
  35. void sieve()
  36. {
  37. ll i,j;
  38. prime.push_back(2);
  39. for(i=3;i*i<=M;i+=2)
  40. {
  41. if(mark[i]==false)
  42. {
  43. for(j=i*i;j<=M;j+=2*i)
  44. mark[j]=true;
  45. }
  46. }
  47. for(i=3;i<=M;i+=2)
  48. {
  49. if(mark[i]==false)
  50. prime.push_back(i);
  51. }
  52.  
  53. }
  54.  
  55. int NOD(int n)
  56. {
  57. int ans=1;
  58. int sqrtN=sqrt(n);
  59. for(int i=0;i<prime.size() && prime[i]<=sqrtN;i++)
  60. {
  61. int x=0;
  62. while(n%prime[i]==0)
  63. {
  64. n=n/prime[i];
  65. x++;
  66. }
  67. sqrtN=sqrt(n);
  68. x++;
  69. ans=ans*x;
  70. }
  71.  
  72. if(n!=1)
  73. ans=ans*2;
  74. return ans;
  75. }
  76. int main()
  77. {
  78. fast_in_out;
  79. //freopen("input.txt","r",stdin);
  80. //freopen("output.txt","w",stdout);
  81. sieve();
  82. int n;
  83. cin>>n;
  84. int ans=NOD(n);
  85. cout<<ans<<endl;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement