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

find smallest odd prime factor of n up to 10^18

Автор mostafaabdelaal_03, история, 11 месяцев назад, По-английски

How I can Find smallest Odd Prime factor of n n<=10^18

we have test cases 10^5

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

»
11 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hi, just factorize n and choose the smallest factor, you can use Pollard's rho algorithm

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

    I think it gets TL because of many test cases

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

      I don't think there is a way that doesn't involve factorization since the prime factors for a composite number could be as large as $$$10^9$$$.

      Pollard Rho is typically $$$\mathcal{O}(\sqrt{\text{smallest prime factor}})$$$ though. Since the input might itself be prime, Miller Rabin to first check primality, followed by Pollard Rho if the number if composite should be sufficient.

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

Problem link?

→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    Problem

    this is my observation

    1-n is odd:..you have to print 2

    2-n is even:

    $$$ n \equiv k*(k-1)/2 \mod{k} $$$

    and if we make k =  smallest odd prime factor of n..

    it will be

    $$$ 0 \equiv 0 \mod{k} $$$

    → Ответить
    • »
      »
      »
      11 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      I don't think a div-1 + div-2 D would require to solve the exact prblm that you mentioned in the blog ,probably it will require something else , observe better

      → Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if there is another easier sol...can you give me a small hint

    → Ответить
    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You found that the equation $$$n \equiv \frac{k(k+1)}{2} \bmod k$$$ must be satisfied for a good $$$k$$$. Is this a sufficient requirement, i.e. is every $$$k$$$ satisfying this also good? Or are there other requirements for a good $$$k$$$? You should try to find sufficient conditions for a good $$$k$$$, preferrably in the form of mathematical equations, and try to find something by playing around with the equations. I can also give more specific hints if you want more help.

      → Ответить