문제 설명

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

제한 사항

• 3 ≤ n ≤ 1,000,000

풀이

자연수 n을 자연수 x로 나누었을 때, 나머지가 1이 되어야 하므로, 반복문을 돌면서 n을 i로 나누었을 때, 나머지가 1이 되는 경우를 반환하도록 구현했다.

JavaScript

function solution(n) {
  var answer = 0;
  for (let i = 1; i < n; i++) {
    if (n % i === 1) {
      answer = i;
      return answer;
    }
  }
}

Python

def solution(n):
    for x in range(1, n):
        if n % x == 1:
            return x

개선

테스트1이 다른 테스트들과 수행 시간이 오래 걸려서, 이를 개선할 방법을 찾게 되었다.

import math

def solution(n):
    target = n - 1
    upper_bound = int(math.sqrt(target)) + 1
    for x in range(2, upper_bound):
        if target % x == 0:
            return x
return target