Number of Divisor of a large number- Code error

general
,
1

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?

2

@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.

3

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
4

Thank you for your valuable inputs.! :stuck_out_tongue:

1 Like
5

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

6

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

7

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
8

here is my implementation see if this helps

1 Like
9

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
10

okay fine … i didn’t see that

1 Like
11

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
12

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

1 Like