# Is there any flaw in the logic of this problem?

The problem is find the number of factors of (N!)^2.

This is the code, I wrote:

int prime[]={//list of primes <(10^6)};
int num_fac_of_factorial(int n, int x)
{
int p=x, z=0;
while(n/p>0)
{
z+=n/p;
p*=x;
}
return z;
}

int count=78498;   //Count of prime numbers <10^6

int main()
{
int n, x, first=0, m=1000007;
long long sol=1;
scanf("%d", &n);

for(int i=0; prime[i]<=n && i<count; i++)
{
x=num_fac_of_factorial(n, prime[i]);
x=2*x+1;
sol=(sol*x)%m;
}
sol%=m;
printf("%d\n", sol);
}


There's no flaw in the logic, just a couple of implementation errors. And if e.g. 1/10 + 1/15 = 1/6 and 1/15 + 1/10 = 1/6 shall not be counted as different solutions but as one, then of course you need (1 + number of divisors)/2.

Here

for(int i=0; prime[i]<=n && i<count; i++)


you ought to check i < count before accessing prime[i]. If n > 999983, you will try to access prime[78498], which is undefined behaviour.

And - assuming that int is as usual 32 bits (or 36, wouldn't apply to 64-bit ints, however) - here

int num_fac_of_factorial(int n, int x)
{
int p=x, z=0;
while(n/p>0)
{
z+=n/p;
p*=x;
}
return z;
}


you have overflow for large enough primes x (typically > 46340) when calculating x*x, which is also undefined behaviour. And with the not uncommon wrap-around for int overflow, that will cause wrong results for n >= 65537. Replace the while loop with

do {
n /= x;
z += n;
while(n > 0);


to avoid the overflow.

• For the first time, I am glad that someone pointed out so many implementation errors in my code. :P Btw, as per the question I need not do (1 + no_of_divisors)/2. That's fine. The i<count should have been before prime[i]<=n. And your point about the int overflow is also right. Thanks for pointing all this out. Apr 6 '12 at 6:42
• Two glitches. You have an interesting definition of 'many' ;) Apr 6 '12 at 9:37
• When you are quite experienced and suddenly make silly mistakes, 'two' indeed is 'many'. :) Apr 6 '12 at 11:18