백준 1929번 소수 구하기

출처 링크:

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

 

처음 나의 풀이

// 에라토스 테네스의 체 이용하기? 근데 이건 소수가 있는 지 없는 지 판별할 때 썼던 것 같은데??



// 각각의 수가 1과 자기 자신을 제외한 약수가 있는지 없는지 판별해야 함
// 1과 자기 자신 사이의 수 중에서 자기자신 나누기 특정 수를 했을 때 나머지가 0인 경우가 있다면 제외처리
// m은 1이상 n은 2이상이 되어야 소수가 적어도 1개 이상 나올 수 있음

// 입력값
const m = 3
const n = 16
let answer = []
let count = 0


if (m === 1) {

  answer.push(2)
  
  for (let i = 2; i <= n ; i++) {

    for (let j = 2; j <= Math.sqrt(i) ; j++) {

      if (i%j === 0) {
      // i가 1과 자기 자신 말고도 나누어지는 정수가 있는 경우, 소수가 아닌 경우
        count++
          }

      // count가 1이상일 경우 i는 소수가 아님
      if (1 <= count) {
        
        count = 0;
        continue;
        
      } else {
        answer.push(i);
        count = 0;
      }

      
      }

      }
  
} else {

    for (let i = m; i <= n ; i++) {

      for (let j = 2; j <= Math.sqrt(i) ; j++) {

      if (i%j === 0) {
      // i가 1과 자기 자신 말고도 나누어지는 정수가 있는 경우, 소수가 아닌 경우
        count++
          }

      // count가 1이상일 경우 i는 소수가 아님
      if (1 <= count) {
        
        count = 0;
        continue;
        
      } else {
        answer.push(i);
        count = 0;
        }
      
      }
  
  }
  
}

console.log(answer)

나름 머리를 굴려가며 풀었지만 예제의 입력과는 다르게 나온다.

잘못된 부분을 짚기 위해 이전에 제출한 풀이를 참조해보았다.

이 풀이는 하단의 링크를 참조하여 제출한 풀이이다.

 

https://velog.io/@gkswn45/JavaScript-백준-1929번-소수구하기

 

 

참조한 풀이를 내식대로 다시 해석해본 것

 

let M = 1;
let N = 5;


/* 배열의 첫 시작은 1이 아닌 0이며 연산을 편히 하기 위해 배열의 길이를 1 늘려줌,
또한 첫 시작인 인덱스 1은 false처리 해주어 답에서 항상 빼주도록 함, 1은 소수에 들어가지 않기 때문 */
const isPrime = Array(N + 1).fill(true);

console.log(isPrime,'isPrime')

// M이 1인 경우는 제외
isPrime[1] = false;

console.log(isPrime,'isPrime22222')


for (let n = 2; n <= Math.ceil(Math.sqrt(N)); n++) { // 에라토스테네스의 체 원리 이용
  if (isPrime[n]) {
    let m = 2; // m이 2부터 시작하기 때문에 n 자기 자신은 그대로 소수 목록에 들어갈 수 있다.
    // Q) 그렇다면 n이 4가 되는 등 소수가 아닌 수가 될 땐 어떻게 되나?
    // A) 이미 n이 2일때 부터 시작했기 때문에 2*2인 4는 앞의 연산에서 false로 제외되었다.
    // 따라서 n자체가 소수가 아닌 경우에도 문제는 없다.
    while (n * m <= N) {
      isPrime[n * m] = false; /* 애초에 n이 자기 자신과 1말고도
      나눌 수 있는 수가 있다는 소리! 소수가 아님 */
      m++;
      //  n과 m 두 수를 1씩 증가 시켜서 하나 하나 확인함
    }
  }
}
console.log(isPrime, "isPrime333333")

const answer = [];
for (let n = M; n <= N; n++) {
  if (isPrime[n]) {
    answer.push(n);
  }
}
console.log(answer, "answer")
console.log(answer.join("\n")); // 자바스크립트의 특성상 자동으로 숫자 -> 문자열로 형변환이 이루어짐

위 내용의 출력 결과는 다음과 같다.

 

[ true, true, true, true, true, true ] isPrime // boolean 형
[ true, false, true, true, true, true ] isPrime22222
[ true, false, true, true, false, true ] isPrime333333
[ 2, 3, 5 ] answer // 숫자형
2 // 문자형
3
5

 

이에 따라 백준에 제출한 양식

 

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split(" ");

let M = Number(input[0]);
let N = Number(input[1]);

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

for (let n = 2; n <= Math.ceil(Math.sqrt(N)); n++) {
  if (isPrime[n]) {
    let m = 2;
    while (n * m <= N) {
      isPrime[n * m] = false;
      m++;
    }
  }
}

const answer = [];
for (let n = M; n <= N; n++) {
  if (isPrime[n]) {
    answer.push(n);
  }
}
console.log(answer.join("\n"));

 

이렇게 정리하긴 했지만

소수 활용 부분은 좀 더 이해와 연습이 필요한 것 같다.

추후 또 복습하여야 겠다.