백준 1929. 소수 구하기

 

문제: https://www.acmicpc.net/problem/1929

 

소수: 1과 자기 자신만을 약수로 가지는 수

 

1. for 문을 반복한 풀이는 시간초과에 걸린다. 

 

2. 약수의 성질과 제곱근을 이용하기 

- 2 이상의 모든 자연수N의 약수는 N의 제곱근을 기준으로 대칭 구조를 이룬다. 

(16의 약수 : 1 , 2 , 4 , 8 , 16 / 가운데 4를 기준으로 2 X 8 = 8 X 2 )  

- 따라서 N의 제곱근까지만 확인해도 약수를 알 수 있다. (약수가 없으면 N제곱근 이후에도 없음)

 

3. [에라토스테네스의 체] 공식을 이용하기 

- 2 , 3 , 4 , ... , N 까지의 수를 나열한 배열에서 소수를 찾는 공식

- 배열의 가장 작은 수 i 는 소수에 포함하고, i의 배수는 모두 제거한다.

- 위의 과정을 반복하면 소수만 남는다. 

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().split("\n");
input = input[0].split(" ");
console.log(solution(+input[0], +input[1]));
function solution(M, N) {
    // console.log("1. 입력값 잘 불러왔는지 확인", M, N);
    const isPrimeNumber = Array(N + 1).fill(true);
    // console.log(
    //     "2. 에라토스테네스의 체 공식을 사용하기 위해 길이가 N인 불리언 배열 생성",
    //     isPrimeNumber
    // );
    isPrimeNumber[1] = false;
    // 3. 1은 소수가 아니니 false 로 처리
    for (let n = 2; n <= Math.ceil(Math.sqrt(N)); n++) {
        //4. N의 제곱근까지로 소수인지 확인할 범위를 좁힌다.
        if (isPrimeNumber[n]) {
            // 5. isPrimeNumber 배열의 n번째 요소를 차례 대로 반복해
            let m = 2;
            while (n * m <= N) {
                // 6. n * m 이 N보다 크지 않을 때 까지만 반복
                isPrimeNumber[n * m] = false; // 7. (n의 m배) 번째에 해당하는 요소는 모두 false로 바꾼다.
                m++;
            }
        }
    }

    const result = [];
    for (let i = M; i <= N; i++) {
        // 8. M ~ N 까지 범위를 설정하고
        if (isPrimeNumber[i]) {
            // 9. i번째 isPrimeNumber가 true 일 때만 (소수일 때만) result에 담는다.
            result.push(i);
        }
    }
    return result.join("\n");
}