fork download
copy 
  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
comments (?)
stdin
copy 
3
16
17
24
stdout
copy 
5
2
8
https://ideone.com/EiLUs2
language:
C++14 (clang 8.0)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!