Algorithm/Baekjoon(Node.js)

[JavaSrcipt] Baekjoon - 4948 : 베르트랑 공준 (Array,fill)

비망노트 2021. 10. 2. 17:19

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

예제입력 예제출력
1
10
13
100
1000
10000
100000
0		 1
4
3
21
135
1033
8392

 

❌ 풀이

const arr=require('fs').readFileSync('/dev/stdin').toString().split('\n').map(x=>Number(x));

for(let i=0;i<arr.length-1;i++){
    let a=arr[i]+1,b=arr[i]*2;
    
    let count=0;
    
    while(a<=b){
        let prime=[];
        for(let j=2;j<=a;j++){
                          
            if(a%j==0){
                prime.push(a);
            }
            if(prime.length>1){
                break;  
            }
            
        }
        if(prime.length==1){
            count++;
        }
        a++;
    }
    console.log(count);
}

깔끔하지못한것도 그렇지만 시간이 7~9초나 걸리게돼서 시간초과가 나온다.

 

 

✅ 다른분의 풀이

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

for (let i = 0; i < inputs.length; i++) {
    let input = Number(inputs[i]);

    let input2 = input * 2;

    let isPrimeNumber = Array(input2 + 1).fill(true);
    isPrimeNumber[0] = isPrimeNumber[1] = false;

    function PrimeNumber() {
        for(let i = 2; i <= Math.ceil(Math.sqrt(input2)); i++) {
            if(isPrimeNumber[i]) {
                let m = 2;
                while(i * m <= input2) {
                    isPrimeNumber[i * m] = false;
                    m++;
                }
            }
        } 
        let results = [];
    
        for(let i = input + 1; i <= input2; i++) {
            if(isPrimeNumber[i]) {
                results.push(i);
            }
        }
        console.log(results.length);
    
    }
    
    PrimeNumber();
}

에라토스테네스의 체를 이용한 이전 1929번문제도 그렇고

다들 true 배열을 쭉 만들고 false로 바꾸는 방식을 많이 사용하시는것같다.

 

입력값의 마지막은 0이므로 pop으로 제거

inputs.pop();

input, input2 선언

isPrimeNumber는 input2+1 만큼의 배열을 만들며 true로 채워준다.

이후 0,1인덱스는 소수가아니므로 false로 바꾸어주고

let input = Number(inputs[i]);

    let input2 = input * 2;

    let isPrimeNumber = Array(input2 + 1).fill(true);
    isPrimeNumber[0] = isPrimeNumber[1] = false;

 

for문에있듯 0 1은 false로 바꾸었고

i=2부터 isPrimeNumber배열의 i인덱스가 참일경우

m=2부터 ++해가며

i*m이 input2보다 작거나 같은동안

isPrimeNumber의 i*m 인덱스를 false로 바꿈

for(let i = 2; i <= Math.ceil(Math.sqrt(input2)); i++) {
            if(isPrimeNumber[i]) {
                let m = 2;
                while(i * m <= input2) {
                    isPrimeNumber[i * m] = false;
                    m++;
                }
            }
        }

즉 i=2부터 input2(최대값)에 루트를 씌운값을 올림한 값보다 작거나 같을때까지

i를 ++하며 isPrimeNumber 인덱스들을 false로 바꾸는것

 

예를들어 input2가 50이라면 루트는 7.xxxx이므로 8까지

2*2 2*3 --- 8*m이 input2보다 작거나같을때까지 해당인덱스를 false

 

n초과 2n이하 이므로

i=input+1 로시작하여 input2보다 작거나같은동안

isPrimeNumber의 인덱스가 true라면 즉 

위의 반복문에서 false로 걸러지지 않은것들 즉 소수를

results배열에 해당 i를 push하고 길이를 출력.

 

 

 

✅ fill

const array1 = [1, 2, 3, 4];

// fill with 0 from position 2 until position 4
console.log(array1.fill(0, 2, 4));
// expected output: [1, 2, 0, 0]

// fill with 5 from position 1
console.log(array1.fill(5, 1));
// expected output: [1, 5, 5, 5]

console.log(array1.fill(6));
// expected output: [6, 6, 6, 6]

구문

arr.fill(value[, start[, end]])

value 채울값 start 시작인덱스 end 끝인덱스

 

 

 

소수로 들어오면서부터 배열을 만들고 채우고

false로 바꾸고... 점점 복잡해진다.

 

 

-출처

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