[백준]2581/소수 /JavaScript

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

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

//입력2
64
65

💬출력 예시

//출력1
620
61

//출력2
-1

---

🍀제출 및 설명

let fs = require('fs');
let input = fs.readFileSync('./dev/stdin').toString().split('\n');

let firstNum = Number(input[0]);
let secondNum = Number(input[1]); 

let primeArr = []

for (let i = firstNum; i <= secondNum; i++) {
    for(let j = 2; j<=i;j++){
        if(i===j){
            primeArr.push(i)
        }
        else if(i%j ===0){
            break;
        }
    }
}

if(primeArr.length === 0 ){
    console.log(-1)
}else{
    console.log(primeArr.reduce((a,b)=>a+b));
    console.log(primeArr[0]);
}

소수는 1과 자신을 제외한 수로 나눠지지 않는다

 

첫번째수 이상 마지막수 이하의 자연수를 for문을 돌리고, 이중 위 조건에 맞는 숫자는 primeArr에 넣는다.

primeNum의 0번째 인자는 두 수 사이 가장 작은 소수이고, 다음 배열을 reduce로 누적합한 값이 사이 소수의 합이다.

 

만약 primeArr에 아무 값도 없는 경우 -1을 출력하였다.

✨다른 풀이

const m = input[0];
const n = input[1];
const prime = [];
const check = new Array(n + 1).fill(false);

for (let i = 2; i <= n; i++) {
  if (!check[i]) {
    prime.push(i);
    for (let j = i * 2; j <= n; j += i) {
      check[j] = true;
    }
  }
}
if(prime[prime.length-1]<m||prime.length===0){
    console.log(-1)
}else{
    console.log(prime.filter((x) => x >= m).reduce((a,b)=>a+b));
    console.log(prime.filter((x) => x >= m)[0])
}

다음은 에라토스테네스의 체방식으로 해결한 방식이다.

식의 방식이 신기해서 가져왔다.

---

 

🐾알고리즘

• 수학
• 정수론
• 소수판정