Блог

Это простой код для подсчета количества общих факторов, которые имеют два числа . Как первый код не превышает ограничение по времени, в то время как второй превышает ограничение по времени. Первый

 from math import sqrt
def gcd(a, b): 
      
    if a == 0: 
        return b 
    return gcd(b % a, a) 

def commDiv(a, b): 
      
    # find GCD of a, b 
    n = gcd(a, b) 
  
    # Count divisors of n 
    result = 0
    for i in range(1,int(sqrt(n)) 1): 
  
        # if i is a factor of n 
        if n % i == 0: 
  
            # check if divisors are equal 
            if n/i == i: 
                result  = 1
            else: 
                result  = 2

    return result


if __name__ == "__main__":
        a , b = map(int,input().split())
        print(commDiv(a, b)) 
        
  

ВТОРОЙ

 a , b = map(int,input().split())
if a>b:
        small = b
        big = a
else:
        small = a
        big = b
c = 0
for i in range(1,small 1):
    if small%i == 0 and big%i == 0:
            c = c   1
print(c)
  

Количество циклов процессора (скорость выполнения) больше зависит от алгоритма, чем от длины вашего кода.

В этом конкретном случае ваше ВТОРОЕ решение имеет цикл, который повторяется small несколько раз. Итак, для, скажем, пары (1200, 700) это будет повторяться 700 раз.

Ваше ПЕРВОЕ решение начинается с нахождения GCD из двух чисел. «Чаще всего» оно будет намного меньше любого числа (если a не делится на b или наоборот). И тогда он повторяется только sqrt(gcd) раз, что в итоге приводит к еще меньшему числу итераций. Для одной и той же пары GCD равно 100, поэтому цикл будет повторяться sqrt(100) == 10 несколько раз. Десять против семисот.

Даже для наихудшего сценария, где a делится b , скажем, на (300000, 10000), ваше ПЕРВОЕ решение будет повторяться sqrt(10000) == 100 несколько раз, в то время как ваше ВТОРОЕ будет повторяться 10000 раз.

Редактировать: следует отметить, что вычисление GCD само по себе занимает несколько циклов процессора, но способ его реализации, он будет повторяться большими шагами и оказывать меньшее влияние на общее время.