백준 1837번 암호제작 JAVA 구현해보기

---

```

백준 1837번 암호 제작 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 1837번 풀이
2.  에라토스테네스의 체 소수 찾기 메서드 사용
3.  큰 수를 사용하는 BIGINT 사용

---

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

1837번: 암호제작

 

 

 

백준 1837번 암호 제작은 

난이도 브론즈 등급의 문제로서

 

두 소수의 곱으로 이뤄진 P

그리고 2부터 10^6 사이의 수로 이뤄진 K가 주어질 때

 

P의 인자인 두 소수중에 하나가 K 미만이면 BAD와 함께 해당되는 소수를 출력하고

두 소수 모두 K 이상이면 GOOD을 출력하면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

저는 일단 10^6 자리 이하인 소수를 모두 구해주었습니다.

그리고 10^100자리인 P가 K보다 작은 수로 나눠진다면 해당되는 수를 BAD와 함께 출력하였습니다.

숫자가 크기 때문에 BIGINT를 사용하였습니다.

 

전체 풀이는 아래와 같습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    final static int SQRT_PRIME_LIMIT = 10000;


    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        final boolean[] isPrime = findPrimeNumbers(SQRT_PRIME_LIMIT);
        String result = "GOOD";
        String pNumStr = st.nextToken();
        String kNumStr = st.nextToken();


        final BigInteger pNum = new BigInteger(pNumStr);
        final int kNum = Integer.parseInt(kNumStr);

        for (int i = 2; i < kNum; i++) {
            if (isPrime[i] && (pNum.remainder(BigInteger.valueOf(i)).compareTo(BigInteger.valueOf(0)) == 0)) {
                result = "BAD " + i;
                break;
            }
        }


        System.out.print(result);
    }

    private static boolean[] findPrimeNumbers(int sqrtPrimeLimitNum) {
        int PrimeLimitNum = sqrtPrimeLimitNum * sqrtPrimeLimitNum;
        final boolean[] isPrime = new boolean[PrimeLimitNum];
        Arrays.fill(isPrime, Boolean.TRUE);

        isPrime[0] = false;
        isPrime[1] = false;

        for (int i = 2; i <= sqrtPrimeLimitNum; i++) {
            if (!isPrime[i]) continue;
            for (int j = i; j < PrimeLimitNum; j += i) {
                if (isPrime[j] && i != j) isPrime[j] = false;
            }
        }
        return isPrime;
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---