Count Divisors

Count Divisors

Solution 1:

Complexity: sqrt(n)

#include<bits/stdc++.h>

using namespace std;

int countDivisors (int n)

{

    int cnt = 0;

    for(int i = 1; i <= sqrt(n); i++){

        if(n % i == 0){

            if(n/i == i)cnt++;

            else cnt += 2;

        }

    }

    return cnt;

}

int main()

{

    int n;

    while(cin >> n && n){

        cout << countDivisors(n)<<endl;

    }

    return 0;

}

Solution 2:

Complexity: O(n^1/3)

#include<bits/stdc++.h>

using namespace std;

void Sieve(int n, bool prime[], bool primesqure[], int a[])

{

    for(int i = 2; i <= n; i++)

        prime[i] = true;

    for(int i = 0; i <= (n*n + 1); i++)

        primesqure[i] = false;

    prime[1] = false;

    for(int p = 2; p*p <= n; p++){

        if(prime[p] == true){

            for(int i = p*2; i <= n; i += p)

                prime[i] = false;

        }

    }

    int j = 0;

    for(int p = 2; p <= n; p++){

        if(prime[p])

        {

            a[j] = p;

            primesqure[p*p] = true;

            j++;

        }

    }

}

int countDivisors(int n)

{

    if(n == 1)return 1;

    bool prime[n+1], primesqure[n*n +1];

    int a[n];

    Sieve(n,prime, primesqure, a);

    int ans = 1;

    for(int i = 0; ; i++){

        if(a[i]*a[i]*a[i] > n)break;

        int cnt = 1;

        while(n % a[i] == 0){

            n = n/a[i];

            cnt = cnt + 1;

        }

        ans = ans * cnt;

    }

    if(prime[n])ans = ans * 2;

    else if(primesqure[n])ans = ans*3;

    else if(n != 1)ans = ans*4;

    return ans;

}

int main()

{

    int n;

    while(cin >> n && n){

        cout << countDivisors(n)<<endl;

    }

    return 0;

}

Share: