[백준 JS] 1837번 암호제작

문제

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하여야 한다.

 

 

입력

암호 P(4 ≤ P ≤ 10^100)와 K (2 ≤ K ≤ 10^6) 이 주어진다.

 

 

출력

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

 

 

풀이

암호의 수준을 판별하는 문제로

앞의 P는 크게 상관할 필요는 없지만 연산을 위해 BigInt로 값을 다뤄야 한다는 부분을 주의해야 하며

K가 100만까지의 숫자기 때문에 결론적으로 K까지의 소수들을 구한 다음

P가 K 이하의 소수 중 하나로 나눠질 경우 BAD와 그 숫자를 출력하고

아닐 경우 GOOD을 출력하는 문제였다.

 

소수 여부를 확인하기 위해서는 소수체크 함수로 모두 체크해도 되겠지만

2부터 k까지의 모든 숫자를 확인해야 하는 문제기 때문에

에라토스테네스의 체를 사용하는 것이 유리하다고 판단했다.

 

소수 판별 배열의 초기값을 1로 만든 다음

해당 숫자의 배수들을 0으로 바꿔주며

소수일 경우 입력된 암호가 그 소수로 나눠지는지 체크해

나눠질 경우 BAD와 그 소수를 출력하는 방식으로 진행했다.

 

BigInt를 중간중간 사용하면서 type Error가 생기지 않도록 주의하고

에라토스테네스의 사용법만 알면 부담없이 해결할 수 있는 문제였다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ')

let num = BigInt(input[0])
let k = Number(input[1])

const arr = new Array(k).fill(1)
let result = "GOOD"

for(let i = 2 ; i <= k ; i ++){
    let bigI = BigInt(i)
    if(arr[i]){
        if(num%bigI === 0n){
            result = `BAD ${i}`
            break
        }
        let n = 2
        while(i*n <= k){
            arr[i*n] = 0
            n++
        }
    }
}

console.log(result)

const input = `143 10`.split(' ')

let num = BigInt(input[0])
let k = Number(input[1])

const arr = new Array(k).fill(1)
let result = "GOOD"

for(let i = 2 ; i <= k ; i ++){
    let bigI = BigInt(i)
    if(arr[i]){
        if(num%bigI === 0n){
            result = `BAD ${i}`
            break
        }
        let n = 2
        while(i*n <= k){
            arr[i*n] = 0
            n++
        }
    }
}

console.log(result)