Alternative of brute force search in python

Here is the problem from AtCoder.
Here is my code to fix,

from itertools import combinations
import math
a,b = map(int,input().split())
x = 0
li = []
for i in range(a,b+1):
    li.append(i)
new_li = list(combinations(li,2))
for i in new_li:
    if math.gcd(i[0],i[1]) > x:
        x=math.gcd(i[0],i[1])
print(x)

I got TLE(Time Limit Exceed) error using this method.
The method that I’m using is that brute force search?
Is there any alternative way to fix this which will be more efficient?

List comprehension can make your code neater.
Also you can pretty much half your time, simply by not calculating the gcd twice. Because at it’s core, this is where your code does most of the work. Just because you only write a quick command, doesn’t mean it’s executed fast.

Then one thing that will help, is this: The gcd of two numbers cannot be bigger than the difference of those two numbers. This can further shave off a lot of time because you can skip a lot of gcd calculations based on that.
Nested for-loops instead of combinations could make that process easier as well, if you know how to implement it.
This could also allow you to implement better starting-values. For example, maybe you could implement an algorithm that looks for the biggest possible gcd first and just stops if it finds it.

That’s all I can think of. There are propably some more advanced methods I don’t know.

One possible way to get those would be to look up how to actually calculate the gcd by hand, then how an algorithm would do this and if there is a way you could modify the 2-input-algorithm so that it fits the problem.

2 Likes

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.