TuHoangAnh's blog

By TuHoangAnh, history, 3 years ago, In English

given an integer $$$n$$$, you have to find $$$a,b>0$$$ so that $$$a+b=n$$$ and $$$LCM(a,b)$$$ is maximum($$$LCM$$$ is the least common multiple of $$$a,b$$$).

printf the maximum $$$LCM(a,b)$$$

i have come up with a bruteforce solution. I will consider all pairs of $$$a,b$$$ that have sum equal to $$$n$$$. And calculate the value of

$$$LCM(a,b)=(a*b)/GCD(a,b)$$$. ($$$GCD$$$ is greatest common divisor).

But, this solution seems too slow when $$$n<=10^9$$$. Is there a better solution for this problem ?

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TuHoangAnh (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If n is even lcm(n/2 +1,n/2 -1) if a and b both are even a+=1,b-=1 and for odd lcm(n-1/2 +1, n-1/2) for even a-b=2 and one of them or both are odd lcm will be nothing but their product and for odd a-b=1 same case here