Блог пользователя DreamingBoy

Нахождение минимального просто делителя быстрее чем за sqrt(N)
Автор DreamingBoy, 7 лет назад, По-русски

Привет CodeForces!

Возможно ли находить минимальное простой делитель для чисел n <= 10 ^ 12, а количество запросов до 10 ^ 5?

Заранее большое спасибо

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Try: Pollard's rho

→ Ответить
»
7 лет назад, # |
← Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

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 !!

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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.

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

→ Ответить