[백준 06219] 소수의 자격 [Java]

문제

6219번: 소수의 자격

6219번: 소수의 자격

 

---

풀이

주어진 A와 B 사이의 소수 중 각 자릿수에 D를 포함하는 소수가 몇개인지 구하는 문제다.

우선 B까지 존재하는 소수를 에라토스테네스의 체로 구해주자.

    private static List<Integer> getPrimeList(int a, int b) {
        boolean[] isPrime = new boolean[b + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        final int sqrtN = (int) Math.sqrt(b);
        for (int i = 2; i <= sqrtN; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= b; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        List<Integer> primeList = new ArrayList<>();
        for (int i = 2; i <= b; ++i) {
            if (isPrime[i]) {
                primeList.add(i);
            }
        }
        return primeList;
    }

B까지의 소수들에 대해, A이상이면서 각 자릿수에 D가 포함되는 수가 있는지 찾으면 된다.

        for (Integer prime : primeList) {
            if (prime >= A) {
                while (prime > 0) {
                    if (prime % 10 == D) {
                        ++cnt;
                        break;
                    }
                    prime /= 10;
                }
            }
        }

풀이 시간

5분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/06219.java

problem-solving/baekjoon-online-judge/easy/06219.java at main · rogi-rogi/problem-solving