Number Of Divisors

#1

Im Getting TLE . So sir i request u to guide for an optimal code . Thank you …

#2

use the approach of factroising the numer and then finding the divisors.
If x=am∗bn∗cp…
where a, b, c, … are the prime factors of x, then the number of factors of x is
(m+1)(n+1)(p+1)…

This is because any factor can be made by selecting 0 to m numbers of a (in m+1 ways), 0 to n numbers of b (in n+1 ways) and so on.

Since 600=23∗3∗52
Total number of factors of 600 = (3+1)(1+1)(2+1) = 24

Have a look here

#3

I am using the same approach as yours but still getting TLE:
// CPP program for finding number of divisor
#include <bits/stdc++.h>

using namespace std;

// program for finding no. of divisors
int divCount(bool hash[],int n)
{
// Traversing through all prime numbers
int total = 1;
for (int p = 2; p <= n; p++) {
if (hash[p]) {

        // calculate number of divisor 
        // with formula total div =  
        // (p1+1) * (p2+1) *.....* (pn+1) 
        // where n = (a1^p1)*(a2^p2)....  
        // *(an^pn) ai being prime divisor 
        // for n and pi are their respective  
        // power in factorization 
        int count = 0; 
        if (n % p == 0) { 
            while (n % p == 0) { 
                n = n / p; 
                count++; 
            } 
            total = total * (count + 1); 
        } 
    } 
} 
return total;

}
int main()
{
long n=1000000;
bool hash[n + 1];
memset(hash, true, sizeof(hash));
for (int p = 2; p * p < n; p++)
if (hash[p] == true)
for (int i = p * 2; i < n; i += p)
hash[i] = false;
long t;
cin>>t;
while(t–)
{
long num;
cin>>num;
cout<<divCount(hash,num)<<endl;
}
return 0;
}