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

문제 설명

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

---

제한사항

• 3 ≤ n ≤ 1,000,000

---

입출력 예

n	result
10	3
12	11

---

입출력 예 설명

입출력 예 #1

• 10을 3으로 나눈 나머지가 1이고, 3보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 3을 return 해야 합니다.

입출력 예 #2

• 12를 11로 나눈 나머지가 1이고, 11보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 11을 return 해야 합니다.

제출답안

1. solution 함수
   1. 먼저 n에서 1을 뺀다.
   2. n-1의 값을 소수 확인 함수에 넣어 값을 리턴받는다.
   3. 만약 해당 함수가 소수가 아니라면
   4. 그러면 2 or 3인 경우가 가장 작은 경우다.
      1. 2로 나눠지면 2를, 아니면 3을 return한다.
   5. 소수인 경우 해당 소수를 반환한다.
2. is_prime_number 함수
   1. x의 제곱근까지 for loop를 돈다.
   2. x와 i를 나누었을 때 0이면 소수가 아니여서
   3. x가 2 또는 3일 경우 False를 반환하고
      1. 아닐 경우 아직 더 나눌 수 있다는 뜻이기에 다시 i값을 넘겨서 재귀 함수를 돈다.
   4. 소수면 x를 반환한다.

import math


def solution(n):
    # 1-1
    minus_one = n - 1
    # 1-2
    is_prime_num = is_prime_number(minus_one)
    # 1-3
    if not is_prime_num:
        # 1-4
        if minus_one % 2 == 0:
            return 2
        return 3
       # 1-5
    return is_prime_num



def is_prime_number(x):
    # 2-1
    for i in range(2, int(math.sqrt(x)) + 1):
        # 2-2
        if x % i == 0:
            # 2-3
            if x == 2 or x == 3:
                return False
            return is_prime_number(i)
    # 2-4
    return x

테스트 1 〉	통과 (0.05ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 9.96MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	통과 (0.00ms, 9.92MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.2MB)
테스트 11 〉	통과 (0.01ms, 10.1MB)