[Python] Lv1.나머지가 1이 되는 수 찾기

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

 

 

 

문제 설명

자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.

 

제한 조건

3 ≤ n ≤ 1,000,000

 

나의 접근방법 및 코드

n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x

→ n % x == 1이라는 것은, 다르게 생각해보면 (n-1)을 x로 나누었을때는 나누어 떨어져야, 즉 나머지가 0이 되어야 한다.

그래서 (n-1)을 2이상 n미만의 범위에서 나누어 떨어지게 하는 수 중, 가장 먼저 나누어 떨어지는 수가 가장 작은 자연수 x가 된다.  

def solution(n):
    answer = 0
    for i in range(2, n):       ## 2부터 n-1까지 나누어 보려고
        if (n-1) % i == 0:      ## 가장 먼저 나누어 떨어지는 수가 가장작은 자연수
            answer = i
            break
    return answer