fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long int;
  4. ll sieve_size;
  5. bitset<10000010>bs;
  6. vector<ll>primes;
  7. void Sieve(ll x){
  8. sieve_size=x;
  9. ll count=0;
  10. bs.set();
  11. bs[0]=bs[1]=false;
  12. for(ll i=2;i<=sieve_size;i++){
  13. if(bs[i]){
  14. for(ll j=i*i;j<=sieve_size;j+=i){
  15. bs[j]=false;
  16. }
  17. primes.emplace_back(i);
  18. count++;
  19. }
  20. }
  21. }
  22. ll CountDivisors(ll x){
  23. ll i=0,PF=primes[i],ans=1;
  24. while(PF*PF<=x){
  25. ll power=0;
  26. while(x%PF==0){
  27. x/=PF;
  28. power++;
  29. }
  30. ans*=power+1;
  31. PF=primes[i++];
  32. }
  33. if(x!=1) ans*=2; // Last factor has pow=1,we add 1 to it
  34. return ans;
  35. }
  36. int main(){
  37. ll n;
  38. cin>>n;
  39. while(n--){
  40. ll x;
  41. cin>>x;
  42. Sieve(x);
  43. cout<<CountDivisors(x)<<"\n";
  44. }
  45. return 0;
  46. }
Success #stdin #stdout 0s 4776KB
stdin
3
16
17
24
stdout
5
2
8