[백준] 1978번 - 소수 찾기 (node.js)

 

 

 

 

[백준] 1978번 - 소수 찾기 (node.js)

문제를 풀던 중 소수찾을때 아주 좋은 공식? 방법인것 같아서 블로그에 올렸다.

 

 

링크

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

 

 

 

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

 

예제

입력 1

4
1 3 5 7

 

출력 1

3

 

 

 

답안

const fs = require("fs");
const [cntStr, str] = fs
	.readFileSync("input.txt")
	.toString()
	.trim()
	.split(/\r?\n/);

const solution = () => {
    const cnt = parseInt(cntStr);
    const arr = str.split(" ").filter((d) => {
        const num = parseInt(d);
        if (num === 1) {
            return false;
        }
        // 소수 찾기의 핵심
        // 소수가 아닌 것을 빼버리면 남은건 소수가 된다.
        // 1과 자기 자신만 자신을 나눈 나머지가 0이 되어야하는데
        // 그 외의것에서 0이 나오면 그것은 소수가 아니다!
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (d % i === 0) {
                return false;
            }
        }
        return true;
    });
    console.log(arr.length);
};

solution();

 

 

 

 

Math.sqrt()의 사용 이유

solution함수 내에서 Math.sqrt(d)을 사용하는 이유는 소수 판별 시간을 줄이기 위함입니다.

숫자 n이 소수인지 판별하기 위해서는 n을 1과 n 자신을 제외한 다른 숫자들로 나누어보며 나머지가 0인지 확인해야 합니다.

그러나 모든 숫자를 확인할 필요는 없으며, n의 제곱근까지만 확인해도 충분합니다.

 

왜 제곱근까지만 확인하면 될까?

• 만약 n이 어떤 수의 제곱이 아니라면, n을 나눌 수 있는 가장 큰 수는 n의 제곱근보다 작습니다.
• 예를 들어, n이 100이라면 100의 제곱근은 10입니다. 100을 나눌 수 있는 수는 1, 2, 4, 5, 10, 20, 25, 50, 100이지만, 이 중 10 이상의 수는 100을 나누는 쌍의 작은 수와 대응됩니다(예: 50은 2와 대응).
• 따라서 n의 제곱근을 초과하는 수로 n을 나눌 필요가 없습니다.
• 제곱근 이하의 수로 나누어 떨어지지 않는다면, 그 이상의 수로도 나누어 떨어지지 않기 때문입니다.

이 방법을 사용함으로써 소수 판별 함수의 실행 시간을 상당히 단축시킬 수 있습니다. 이는 특히 n이 매우 큰 수일 때 효과적입니다.