[백준] 2581번 - 소수 (node.js)

 

 

 

 

 

[백준] 2581번 - 소수 (node.js)

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하여 주어진 범위 내에서 모든 소수를 찾는 데 사용됩니다. 이 알고리즘은 특정 범위 내의 모든 소수를 효율적으로 식별할 수 있는 방법입니다.

여기서는 배열 isPrime을 사용하여 각 숫자의 소수 여부를 표시합니다.

과정은 다음과 같습니다:

 

 

링크

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

 

 

 

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

 

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

 

 

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

 

 

예제

예제 입력 1

60
100

 

예제 출력 1

620
61

예제 입력 2 

64
65

 

예제 출력 2

-1

 

 

 

 

답안

const fs = require("fs");
const numArr = fs
	.readFileSync("input.txt")
	.toString()
	.trim()
	.split(/\r?\n/)
	.map((d) => parseInt(d));
    
    
const [start, end] = numArr;

const isPrime = Array(end + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;

마지막 숫자의 제곱근가지 루프돌리고 //
for (let i = 2; i <= Math.sqrt(end); i++) {
	곱셈있는 값들 (소수가 아닌값들)에 해당하는 값에 해당하는 배열자리 다 false //
	for (let j = i * i; j <= end; j = j + i) {
        isPrime[j] = false;
    }
}

남은 자리는 소수에 해당하는 배열 자리 // 
그 자리를 숫자로 치고 배열에 넣고 //
const primeArr = [];
for (let i = start; i <= end; i++) {
	if (isPrime[i]) primeArr.push(i);
}

이후에 계산 //
if (primeArr.length === 0) {
	console.log(-1);
} else {
	console.log(primeArr.reduce((acc, cur) => acc + cur));
    console.log(Math.min(...primeArr));
}