[백준 / BOJ] 4134번 다음 소수 (Javascript / Node js)

https://www.acmicpc.net/problem/4134

4134번: 다음 소수

문제 해석

문제 자체는 간단하고 명확하다, 테스트 케이스마다 입력받은 n보다 큰 소수 중 가장 작은 소수를 출력하면 정답이다.

즉, n 바로 다음에 나올 소수가 정답이 되겠다.

 

 

이번에도 마찬가지로 정수 n의 범위가 1억을 가볍게 넘기는걸 보니 단순한 for문으로는 반드시 시간 초과가 걸릴 것이다.

 

1. 일단 단순하게 시간 초과를 고려하지 않고 n 바로 다음에 나올 소수를 찾기 위해선 for문과 n++ 을 통해 n에서 1씩 증가시키고 증가된 값을 i라고 가정했을 때 i가 본인과 1을 제외한 약수가 있는지 for문으로 검사해주면 되겠다.

 

 

 

2. 문제는 1번과 같이 구현을 했다간 n이 1억 이상의 값이 들어왔을때 약수의 존재를 검사할때 for문이 1억 이상 돌아간다는 것이다. 시간초과가 안날래야 안날 수가 없다.


이를 해결하기 위해 for문의 범위를 i <= n 이 아닌 더 작게 잡을 방법을 생각했다.

해결방법은 i <= sqrt(n) 으로 잡는 방법이다. 아래 예시로 설명하겠다.

 

21의 약수는 [1, 3 , 7 , 21] 가 있다.  하지만 이 약수들 전부를 일일히 mod 연산을 하지 않아도 21가 약수가 아니라는 걸 검증할 수 있다. 

모든 수 n의 약수들은 모두 쌍을 이루고 있다. ex 12 => 1, 2 ,3 ,4 ,6, 12 => (1 x 12), (2 x 6), (3 x 4)
때문에 3 을 갖고 21 mod 3 연산을 해도 3 의 페어인 7 은 검사하지 않아도 21의 약수라는걸 알 수 있기 때문이다.

그리고 이 페어들 중 작은 수, (ex 12 => 1 , 2 , 3)의 최대값은  n의 제곱근보다 클 수 없다.
왜냐하면 만약 작은수가 n의 제곱근 보다 크다면 그 페어의 곱은 반드시 n보다 클 수 밖에 없기 때문이다.

 

3. 이제 위 내용을 활용하면 n이 1억이 들어왔다고 해도 for문의 실행 횟수는 10000밖에 되질 않는다. 

 

 

전체 코드

const fs = require("fs");

const input = fs.readFileSync("../input.txt").toString().trim().split("\n").map(item => Number(item));

input.shift();

const prime = (n) => {
    if(n < 2){
        return false;
    }
    for(let i=2; i<= Math.sqrt(n); i++){ //for 문의 범위를 n 의 제곱근으로 설정
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

let answer = [];

for(let i of input){ //input 에는 모든 테스트 케이스가 들어있음
    while(!prime(i)){ //n 을 1씩 증가시키고 prime() 함수로 소수인지 검사받은 후 소수가 아니라면 1증가
        i++;                  //소수가 나올때까지 while 문이 실행된다.
    }
    answer.push(i);
}

console.log(answer.join("\n"));

 

-끝-