자연수 n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 반환하는 함수 구현하기
자연수 n
이 매개변수로 주어집니다. n
을 x
로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x
를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.
n
≤ 1,000,000
n | result |
10 | 3 |
12 | 11 |
자연수 n을 자연수 x로 나누었을 때, 나머지가 1이 되어야 하므로, 반복문을 돌면서 n을 i로 나누었을 때, 나머지가 1이 되는 경우를 반환하도록 구현했다.
function solution(n) {
var answer = 0;
for (let i = 1; i < n; i++) {
if (n % i === 1) {
answer = i;
return answer;
}
}
}
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