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

# 문제 원문

 

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

---

제한사항

• 3 ≤ n ≤ 1,000,000

---

입출력 예

n / result

10	3
12	11

 

# 문제 풀이

입력 받은 n을 나누었을때 1이 남는 수중 가장 작은 수를 찾는 문제이다. 그냥 1부터 계속 1씩 증가시키면서 1이 남는 수를 찾아도 상관은 없지만 그럴 경우 큰 수의 경우 매우 비효율적이라서 값으로 나올수 있는 2가지 경우인 n - 1과 n - 1의 약수 2가지 경우에 맞춰서 확인했다. 2부터 시작해서 int * int  <=  n - 1의 범위까지 약수가 있는지 확인하고 있으면 약수를 반환하고 없으면 n - 1를 반환해주면 된다.(결과 값이 소수인지 검증하는 것, 소수일 경우 약수가 없고 소수가 아닐 경우 약수가 있다.)

 

# 솔루션 플로우

1. 입력 받은 n - 1을 하여서 조건에 부합하는 가장 큰 수 target을 구한다.

2. 2부터 반복하여서 target의 약수를 구한다.

3. 약수가 있으면 target의 약수를 없으면 target을 반환한다.

1. 반복문을 활용한 풀이

function solution(n) {
    const target = n - 1;
    let result = target;
    for (let int = 2; int * int <= target; int++) {
        if (target % int === 0) {
            result = int;
            break;
        }
    }
    return result;
}