[JavaScript] 백준 기본수학2 #1929번 소수 구하기

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

1929번: 소수 구하기

---

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

예제 입력1

3 16

 

 

예제 출력1

3
5
7
11
13

 

 

해결 방법

두 가지의 방법으로 해결했다.

1. 소수 찾는 함수를 만들어서 for문을 이용해서 범위 내에서 함수 호출하기

2. 에라토스테네스의 체 방법 사용하기

 

1번의 경우 답안을 제출하고 한동안 채점이 진행되지 않아서 틀린 답안인가 보다 하고 2번 방법을 찾아서 진행했다. 그런데 한 30분 후에 맞았다고 채점된 ㅋㅋㅋ 

 

2번의 경우 에라토스테네스의 체란 모든 자연수는 소수의 곱으로 이루어져 있다는 원리를 이용한 것이다. 범위 내에서 2부터 시작해서 2 자신을 제외한 배수를 모두 지운다. 다시 3부터 시작해서 3을 제외한 모든 3의 배수를 지운다. 이렇게 소수의 배수들을 지우다 보면 결국 소수만 남는 방법을 이용한 것이다.

에스토스테네스의 체 -위키백과

전체 코드

1번 방법

const fs = require('fs');
let [M, N]= fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

const arr = []; //소수가 들어갈 빈 배열 생성

function prime(n){
    if(n<=1) return;  //값이 1보다 작은 경우 소수가 아니므로 리턴
    for(let i=2; i*i<=n; i++){ //제곱근을 사용해도 되지만 코드의 간결함을 위해 제곱값을 사용
        if(n % i === 0) return; //만약 나눈 값의 나머지가 0이라면 소수가 아니므로 리턴
    }

    arr.push(n); //리턴되지 않은 소수값들을 빈 배열에 넣어준다.
}

for(let i=M; i<=N; i++){ //범위 값을 for문으로 지정
    prime(i); //범위 값의 수마다 정의함 prime 함수 호출
}

console.log(arr.join('\n')); //결과 값이 담긴 배열을 줄바꿈 포함하여 문자열로 합친다.

 

 

2번 방법

const fs = require('fs');
let [M, N]= fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

let primeNumber = Array(N + 1).fill(true); //범위 값만큼 ture로 채운다. (true === 소수)
primeNumber[0] = primeNumber[1] = false; //0과 1은 소수가 아니므로 false로 설정


    for(let i=2; i*i<=N; i++){  //제곱근 또는 제곱 값으로 범위 설정
        if(primeNumber[i]){  //만약 true 라면
            let n = 2;  //곱해주는 값 지정(i는 소수이므로 2부터 시작)
            while(i * n <=N){  //i 곱하기 n이 범위 값을 넘지 않을 때까지 반복
                primeNumber[i * n] = false;  // 곱한 값(=소수의 배수)를 false로 지정
                n++; //n 에 1을 더한다. (i가 2라면 2x2, 2x3, 2x4 ...이렇게 배수가 false로 지정되는 것)
            }
        }
    }

    const arr = []; //결과 값이 들어갈 빈 배열 설정
    for(let i=M; i<=N; i++){ //for문으로 범위 값 지정
        if(primeNumber[i]){ //값이 true라면
            arr.push(i); //배열에 넣어준다.
        }
    }

    console.log(arr.join('\n')); //결과 값들을 줄바꿈을 포함하여 문자열로 함친다.

2번 방법은 다른 블로그 글을 참고하였다.

 

 

참고 사이트

https://velog.io/@gkswn45/JavaScript-%EB%B0%B1%EC%A4%80-1929%EB%B2%88-%EC%86%8C%EC%88%98%EA%B5%AC%ED%95%98%EA%B8%B0

JavaScript 백준 1929번 소수구하기

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전