[프로그래머스] 나머지가 1이 되는 수 찾기: python3

def solution(n):
    # n-1의 가장 작은 약수 구하기
    # x>1
    n = n-1

    for d in range(2, int(n**(0.5))+1): # 약수찾기
        if n % d == 0:
            return d

    return n

<내 풀이 분석>

문제를 n-1의 1이 아닌 가장 작은 약수 구하는 문제로 재해석함

          // n = Q*x + 1 (x>1)

          // n-1 = Q*x (x>1)

1. n = n-1

2. 2부터 sqrt(n)까지의 숫자로 n을 나눠본다.(sqrt(n)까지만 찾아도 충분히 찾을 수 있다.) 만약 나머지가 0이 되는 수가 있다면 그 수를 반환한다.

3. 이 숫자 중 약수가 없다면 소수이므로, 1과 자기자신밖에 약수가 없게 된다. => 자기 자신 반환

 

+) 약수를 루트n까지만 찾아도 되는 이유

ex) 18의 경우 sqrt(18)까지 찾아보면 2,3이 나옴, 나머지는 이를 이용해서 구할 수 있음 => 18/2(=9), 18/3(=6)

만약, sqrt(18)까지 약수가 없다면 그 뒤의 수를 나눠봐도 어차피 안나옴(불필요한 계산).