문제

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

제한사항

• 3 ≤ n ≤ 1,000,000

입출력 예

입출력 예 설명

• 입출력 예 #1

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

• 입출력 예 #2

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

✍ 코드 - 초기 풀이

# (1)

from primePy import primes

def solution(n):
    answer = 0 

    primes_to_n = primes.upto(n)
   
    print(primes_to_n)


    for i in primes_to_n:
        if n % i == 1:
            print(i)

			answer = i
            break

    return answer

n = 10
print(solution(n)) # 출력 예 : 3 

• (1) : 이 문제는 소수를 이용하여 문제를 해결하고자 했다. 주어진 숫자가 n일 때 n이하의 모든 소수를 판별하고 n을 n 이하의 소수로 나눴을 때 나머지가 1이 나올 수 있게 하는 모든 소수 중 가장 작은 소수가 나올 수 있도록 하기 위해서 primePy 라이브러리의 primes를 import 하려고 했었다. 프로그로밍 상에는 문제가 발생하지 않았으나, 해당 문제를 프로그래머스 내에서 코드 실행을 하면
  와 같은 메시지가 출력됐다. 따라서 이 방식은 프로그래머스 상에서는 적합하지는 않았다. 그러나 primePy 라이브러리라는 존재를 알게 된 것에 만족한다.

✍ 코드 - 최종 풀이

def solution(n):
    answer = 0 

    # (1)
    sieve = [True] * n

    # (2)
    m = int(n ** 0.5)

    for i in range(2, m + 1):
        if sieve[i] == True: # (3)
            for j in range(i+i, n, i): # i (4)
                sieve[j] = False

    # (5)
    # (6)
    seive_list = [i for i in range(2, n) if sieve[i] == True]

    # (7)
    # (8)
    for value in seive_list:
        if n % value == 1:
            answer = value
            break

    return answer

n = 12
print(solution(n)) # 출력 예 : 3

• 해당 문제는 '에라토스테스의 체' 방법을 활용해서 문제를 풀었다.
• (1) : 에라토스테네스의 체 초기화 : n개 요소에 True 설정(소수로 간주)
• (2) : n의 최대 약수가 sqrt(n) 이하이므로 i = sqrt(n)까지 검사
• (3) : i가 소수인 경우
• (4) : i 이후 i 배수들을 False 판정
• (5) : sieve를 통해 얻은 소수 목록을 seive_list에 대입
• (6) : 참고로 seive 자체의 리스트 요소들을 True 또는 False로 이루어짐
• (7) : seive_list 안에 있는 소수 요소들 중에서 문제가 요구하는 가장 작은 수 찾기
• (8) : 가장 작은 수를 찾으면 for문을 종료함

📝 결과

😃 느낀점

• '에라토스테스의 체'에 대해서 처음 알게 되었다. 만약 나였다면 2부터 n까지 하나하나 구했을 것 같은데, 시간을 더 절약할 수 있는 방식을 알게 되어 뿌듯하다.
• 또한, 초기 풀이에서 PrimePy 라이브러리에 대한 것도 알게 되었다. 사실 Visual Studio에서 실행 시간만 놓고보면 PrimePy 라이브러리로 돌리는 것이 '에라토스테스의 체' 보다 훨씬 빠르지만, 프로그래머스에서는 실행이 안되니 이 점은 다소 아쉬웠다.

👍 Irish의 모든 코드 보기

-> Irish Github