백준 2581 소수 [JavaScript]

문제

자연수 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

풀이

//2부터 X-1까지 모두 나눠서 X가 소수인지 판별하는 문제 2
const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const M = parseInt(input[0]);
const N = parseInt(input[1]);

let sum = 0;        //소수의 합
let min = -1;        //소수 최솟값

for(let i=N; i>=M; i--){    //m이상 n이하의 자연수 중 소수 판별
    let div = Math.floor(Math.sqrt(i));
    let noprime = 0;      //소수 판별 변수
    if(i===1){		//1은 소수가 아니므로 판별 통과
        continue;
    }
    for(let j=2; j<=div; j++){
        if(i%j === 0){          //소수가 아니므로 반복문 탈출
            noprime++;
            break;
        }
    }
    if(noprime === 0){      //소수이므로
        sum += i;
        min = i;
    }
}
if(sum !== 0){
    console.log(sum);
}
console.log(min);

해설

백준 1978 소수찾기에서 얻은 교훈으로 소수를 판별하기위해 그 수의 제곱근까지만 나누어서 찾고자 하였다.

최솟값을 쉽게 구하기 위해 n부터 수를 감소시키며 반복문을 돌게 하였다.(마지막 소수가 가장 작은 소수이므로 min에 저장된다.)

소수인지 판별하는 수를 2부터 제곱근까지 나누어서 딱 떨어지면 소수가 아니므로(1과 자기자신이 아닌 다른 수로 나누어떨어지니까) 배제하고 다 돌았을 때까지 딱 떨어지지 않았다면 소수이므로 더해주어 합을 구하였다.