# NumberOfDivisors

May 4th, 2021
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. using namespace std;
3. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
4. #define ll long long
5. #define pb push_back
6. #define endl "\n"
7. const int mx = 1e6+123;
8. vector<int>primefactorization[mx];
9. bitset<mx> is_prime;
10. vector<int> prime;
11.
12. void primegen ( int n )
13. {
14. n += 100;
15. for ( int i = 3; i <= n; i += 2 ) is_prime[i] = 1;
16.
17. int sq = sqrt ( n );
18. for ( int i = 3; i <= sq; i += 2 ) {
19. if ( is_prime[i] == 1 ) {
20. for ( int j = i*i; j <= n; j += ( i + i ) ) {
21. is_prime[j] = 0;
22. }
23. }
24. }
25.
26. is_prime[2] = 1;
27. prime.push_back (2);
28.
29. for ( int i = 3; i <= n; i += 2 ) {
30. if ( is_prime[i] == 1 ) prime.push_back ( i );
31. }
32. }
33. ll NOD(ll l)
34. {
35. int ret=1,cnt=1;
36. for(auto p: prime)
37. {
38. if(1LL*p*p >l) break;
39. if(l%p==0)
40. {
41. cnt=1;
42. while(l%p==0)
43. {
44. cnt++;
45. l/=p;
46. }
47. ret*=cnt;
48. }
49. }
50. if(l>1) ret*=2;
51. return ret;
52. }
53. int main()
54. {
55. suni;
56. primegen(1e6);
57. int t; cin>>t;
58. while(t--){
59. ll n;
60. cin>>n;
61. cout<<NOD(n)<<endl;
62. }
63. return 0;
64. }