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

출처 : https://programmers.co.kr/learn/courses/30/lessons/87389

코딩테스트 연습 - 나머지가 1이 되는 수 찾기

 

#구하려는 수에 -1한 수의 약수 중 1을 제외하고 가장 작은 수를 return
from math import sqrt

def isDivider(dividend):
    for i in range(2, int(sqrt(dividend)) + 1):
        if dividend % i == 0:
            return i

def solution(n):
    return isDivider(n-1) or n-1

 

자연수 n이 있을 때, n을 x로 나눈 나머지가 1이 된다면,

 

x * a + 1 = n

(n -1) / a = x

 

이므로 x는 n-1의 약수이다.

이 중 1은 모든 수를 나누어 떨어지게 하므로 1을 제외한 가장 작은 약수를 return하면 된다.

 

여기서는 자연수 2부터 제곱근(n-1)을 정수화 + 1한 수까지 중 가장 작은 수를 찾으면 바로 return하고

이 중 나누어 떨어지는 수가 없다면 or n을 통해 n-1을 return해준다.

 

python에서 or은 앞에가 false(null)이면 뒤의 값을 return한다.

즉, 자연수 2부터 제곱근(n)을 정수화 + 1한 수 사이에서 약수가 없다면 이와 세트로 맞물리는 수도 없으므로

1과 맞물리는 n-1만이 1보다 큰 약수 중 가장 작은 수가 되기 때문이다.

 

return isDivider(n-1) or n-1