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

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

I used an prime factorization of the final number x as follows

Assume x exists and = p1^q1 * p2^q2... and so on where p1<p2<p3<....

For the largest divisor I divide x by p1 so b=x/p1;

Now for second largest (i.e. a) I have two choices I have to compare between p1^2(if q1=1 then we don't have this choice) and p2 If p1^2>p2 then the second largest should be a=x/p2; else a=x/(p1^2);

consider the first one x/p2=a; and x/p1=b; or, a*p2=b*p1; Eq-1

let m be the gcd of (a,b) then dividing both sides of Eq-1 by m(let a/m=a1 and b/m=b1) a1*p2=b1*p1; now a1 doesn't have any common factors with b1 so it completely divides p1 similarly, p1 doesn't have any common factor with p2 so it completely divides a1

Hence a1=p1 and b1=p2;

So if a1 and b1 are not primes this fails as we don't get them as the largest and second largest numbers.

now considering the second case.(Only applicable if q1>1) a=(x/p1^2) and b=(x/p1)
or, p1^2*a=b*p1 or, p1=(b/a);

Hence it is clear that if a divides b and b/a is prime then only it holds otherwise it fails

I am not quite sure whether there are some more conditions or Am i missing something?

I submitted my code, It ran cause the test cases were only those which have a and b as answers
239748609

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

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

Well, you did exactly what I did.

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

    Yea, I am still thinking is there some more conditions.

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

      There is only 2 types of number pairs, and you proved when they failed and when they didn't. So I have no reason to say that you ( we ) missed any condition.

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

nice

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

grt