aritra2zk9l's blog

By aritra2zk9l, history, 5 months ago, In English

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

Full text and comments »

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