Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

abdelaal_03's blog

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

By abdelaal_03, history, 3 years ago, In English

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

we have test cases 10^5

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

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

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

    I think it gets TL because of many test cases

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

      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.

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

Problem link?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it -11 Vote: I do not like it

    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} $$$

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +11 Vote: I do not like it

      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

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

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

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

      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.

      → Reply