[1929] 소수 구하기 Find decimals

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

My solution

소수 찾기는 이미 2번 정도 풀어본 흔한 기출문제였다. 기본적으로 알고 있는 방식으로 소수를 판정할 수 있지만 입력이 너무 커지면 시간복잡도가 엄청나게 늘어나게 된다. 그래서 효율성면에서 fail이 나오는 문제들이 있다. 소수 판정에 막혀봤을 때 한참 고민해보다가 에라토스테네스의 체 라는 걸 알게 되었다.

해당 숫자가 가지고 있는 약수를 나열해서 반으로 나누었을 때 앞쪽 부분에 있는 것들이 뒷쪽 부분의 숫자와 곱해서 해당 숫자를 만들어낸다. 따라서 앞쪽 부분의 숫자만 검사해도 이 값이 소수인지 판단할 수 있다는 것이다.

16의 약수 1 2 4 8 16을 예로 들면, 1,2,4만 검사하면 소수임을 판정할 수 있다.

17의 약수 1, 17을 예로 들면 17의 제곱근인 4.xxx보다 작은 숫자 1,2,3,4만 검사해도 소수인지 알 수 있다. 나머지 뒷부분은 앞부분의 숫자들의 배수로 만들어지기 때문이다.

들어오는 숫자가 1이하인 경우에는 소수가 아니고, 2인 경우는 1과 2(자기자신)를 약수로 가지므로 소수가 맞다. 이러한 에지 케이스를 처리한 다음 for문으로 약수가 존재하는지 확인한다.

소스코드

function isPrime(num) {
    if (num <= 1) return false;
    if (num === 2) return true;

    for (let i = 2; i <= Math.floor(Math.sqrt(num)); i++)
        if (num % i === 0) return false;

    return true;
}

function solution(numbers) {
    let answer = [];
    let nums = numbers.split(" ").map((v) => parseInt(v));

    for (let i = nums[0]; i <= nums[1]; i++) if (isPrime(i)) answer.push(i);
    console.log(answer.join("\n"));

    return answer.join("\n");
}

test("solution", () => {
    expect(solution("3 16")).toBe("3\n5\n7\n11\n13");
});