4
\$\begingroup\$

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);
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 6 '12 at 6:42
  • \$\begingroup\$ Two glitches. You have an interesting definition of 'many' ;) \$\endgroup\$ Apr 6 '12 at 9:37
  • \$\begingroup\$ When you are quite experienced and suddenly make silly mistakes, 'two' indeed is 'many'. :) \$\endgroup\$ Apr 6 '12 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.