Number of Divisor of a large number- Code error

I am using the following code to calculate the number of Divisor of a large number(10^16 order). Code Link:- https://ideone.com/eBnZ37 (The output for 11 should be 2 whereas it’s giving me 4).

This implementation was provided here:- https://discuss.codechef.com/questions/96880/calculate-number-of-factors-of-a-large-number?page=1#96889. by @adhish_kapoor

It uses Sieve, Miller Rabin and finally calculates no of factors in O(N^1/3) using this algorithm :- http://codeforces.com/blog/entry/22317 .

However I am getting a wrong output. Can someone please help me in figuring out what is wrong with this code?

@horcrux2301 this question seems to be related to April Circuits 2017 on hackerearth.
Doesn’t it?
The contest will be completed within few hours then you can check the editorial.

The error is in this segment-

if(Miller(n))
  {
    ans = ans*2; // ans2 to ans*2
  }
  else if(sq*sq == n && Miller(sq)) // sqsq to sq*sq
  {
  ans = 3;
  }
  else if(n != 1)
  {
  ans *= 4;
  }

Minutely observe the segment-

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

In case of prime number 11 (as you took), our loop exits at prime 3 (if i understand the working correctly) and before it, no prime is able to divide n=11 (in your case). The value of ans was 1 after the loop and after the if-else it becomes 4. I think the problem is that either prime numbers were not considered while writing the program,
or it might be the “Miller” function (Since it is making ans x 2 and would give correct answer of 2 if executed) .

1 Like

Thank you for your valuable inputs.! :stuck_out_tongue:

1 Like

You can solve for any N in O(N^1/3) easily. refer to :- http://codeforces.com/blog/entry/22317 to find the error in your code . hope it works

http://codeforces.com/blog/entry/22317
go to this site and solve your problem

I think I found the problem, in line no. 129 change

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

to

else if(n != 1)
{
    ans *= 2;
} 

Sample input >>>>>>>> output

01 >>>>>>>>>>>>>>>>>>>> 1

13 >>>>>>>>>>>>>>>>>>>> 2

12 >>>>>>>>>>>>>>>>>>>> 6

Failing for n : 6, 25, 30, 35, 36, …, 100

I think we are missing one condition, try to think from a different point of view…

1 Like

here is my implementation see if this helps

1 Like

Yup, thats what i said. But theres 1 more thing to consider. Above it is

` if(Miller(n))
{
ans = ans2; // ans2 to ans2
}

I feel it might be possible that a big in miller is causing prime numbers to go to below if (while intention was they get executed in this if only). What are your views?

1 Like

okay fine … i didn’t see that

1 Like

Most probably any condition is missing in “if(Miller(n))” block.

And sorry for posting the same, I didn’t read your full answer :stuck_out_tongue:

1 Like

I just wanted to know your opinion on that Miller(n) thing. Nothing else :slight_smile:

1 Like