Python을 사용하여 N이 2에서 N까지의 숫자로 Coprime인지 찾는 시간 복잡성을 향상시키는 방법은 무엇입니까?

질문

나는 내 코드를 작성했으며 두 개의 숫자가 coprime인지 아닌지 확인하는 두 가지 메서드 coprime () 와 count_coprime () 로 구성됩니다. code> n작동하지만 너무 느리고 개선을 찾고 있습니다.

1 위 :

def coprime(a, b):
    # Returns a boolean value
    # Returns true if a and b are in fact coprime
    if a == 1 or b == 1:
        return True
    else:
        count = 0
        if a < b:
            for i in range(2, a + 1):
                if a % i == 0:
                    if b % i == 0:
                        count += 1
        else:
            for i in range(2, b + 1):
                if b % i == 0:
                    if a % i == 0:
                        count += 1
        return count < 1

2 위 :

def count_coprimes(n):
    count = 1
    for i in range(2, n):
        if coprime(i, n):
            count += 1
    return count

답변1

두 숫자가 코 프라임인지 확인하려면 GCD ( Great Common Diviso r) 알고리즘을 사용할 수 있습니다. gcd (a, b) == 1 이면 값은 coprime입니다. O (max (log (a), log (b)))시간에 작동하므로 전체 호환성은 O (nlogn) 입니다.

표준 수학 모듈에는 이미 math.gcd ()함수가 포함되어 있습니다. Euclid 알고리즘의 간단한 구현 :

def EuclideanGCD(x, y): 
    while y: 
        x, y = y, x % y 
    return x 

 

 

 

 

출처 : https://stackoverflow.com/questions/63048576/how-to-enhance-the-time-complexity-of-finding-if-n-is-coprime-with-the-numbers-f