DreamingBoy's blog

How to find the minimal prime divisor, faster than sqrt(N)
By DreamingBoy, 8 years ago, translation, In English

Hello CodeForces How to find minimal prime divisor for n <= 10^12 if there are number of queries <= 10^5

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Try: Pollard's rho

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

check the number by each prime number less than 10^4 till it get it smallest prime factor which are around 1200 so it can be done. if prime number less than 10^4 is not factor so it is clear that n have all prime factor greater than 10^4 therefore n can have maximum two no. of factor than there are only three possibility that either

1- Number is itself is prime number so it can be check using Miller Rabin algorithm in O(k(logn)^3)

2- Number is square of prime number so again it can be check

3- Number is product of two distinct prime number. Using Pollard Rho Algorithm we can find the factor of number and smallest number will be smallest prime factor of number in O(n^1/4)

It will be done in O(10^3) Hope it Help!! Sorry for bad English !!

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I could never use that Miller Rabin, I always get WA by that.

    Is there any good and reliable c++ code for the algorithm?

    NOTE : I don't even know the algorithm and don't wanna know it too :). Just need a code.

    Also the third part happens when first and second are rejected, You don't have to check it by weird algorithms...

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

      Here is my code Miller Rabin. I didn't get WA till now but now also if you get the WA from this code please ping me so that i can correct my code

      In the question we need to apply third part because we need to find smallest prime factor.

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

        I tested your code on some problem and it was OK...

        Thank you ;)

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

Store the primes less than 10^6 and factorise by iterating over primes less than sqrt(N). Complexity will be around sqrt(N)/logN.

→ Reply