vsanjay_nitdgp's blog

10^18 prime factorisation...??
By vsanjay_nitdgp, history, 9 years ago, In English

could any one post code for the followong question.

PROBLEM :F ,GYM

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This question is pretty simple if you have Pollard Rho algorithm in your library. It's a straight copy and paste.

Here you go :

http://ideone.com/3dnYAv

Note: I think there is some way ( which I don't know ) to solve this question without this algorithm.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Blog Post

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First remove all prime factors that are less than 10^6. Let x be the resulting number. Now check if x is prime or not using miller-rabin. If it is prime then we already have the prime factorization. If x is not prime we know that the remaining prime factors are greater than 10^6, therefore it must have exactly two prime factors (since having 3 or more would yield a number greater than 10^18). Now we need to know whether those prime factors are equal or not, we can simply check if x is a square or not, we can do this be testing if x == pow(int(sqrt(x) + .5), 2). With these you should be able to get the number of divisors.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Correct me if I'm wrong, but isn't miller rabin unreliable especially for programming contests?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Is it garanteed that x == pow(int(sqrt(x) + .5), 2) works for every case (precision loss)?? I remember doing something similar and getting wrong answer, so I just iterated from sqrt(x)-5 till sqrt(x)+5 to avoid that, though probably sqrt(x) and sqrt(x)+1 are enough.

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

here is a recent blog post by himanshujaju.

→ Reply