백준 6219 자바 - 소수의 자격 (BOJ 6219 JAVA)

문제 : boj6219

 

 

1. 우선 A, B 사이의 소수를 어떻게 효율적으로 구할까?

  에라토스테네스의 체 방식을 사용하여 미리 구해두면 된다. 이 때 내 경우엔 좀 더 효율적으로 하고자 sqrt(n)까지만 확인(왜 그래도 되는지는 여기를 확인해보면 된다.)하고, 짝수는 굳이 안봐도 되므로 아예 확인하지 않는 등의 약간의 추가 처리가 들어가있다. 코드에서 getPn()을 확인해보면 된다.

 

2. 다음으로 어떠한 정수가 있을 때 해당 수에 숫자 D가 포함되는지 어떻게 알 수 있을까?

  가장 간단하게는 해당 정수를 String으로 변환하고 숫자 D도 character로 변경해서 확인해보는 방법이 있다. 당연히 좀 비효율적이다. 좀 더 빠르게 하려면 나머지 연산과 나누기 연산을 사용하면 된다.

어떠한 n에 대해 n%10으로 일의 자리의 수를 확인하여 D인지 확인한다. 아니라면 n을 10으로 나눈다.(n=n/10)

이걸 D를 발견하거나, n이 0이 될때까지 반복하면 된다. 코드에서 for (int pn : pns) 부분을 확인해보면 된다.

 

3. 전체 로직은 그럼 다음과 같다.

A. 에라토스테네스의 체로 A, B 사이의 모든 소수를 구한다.

B. 'A'에서 구한 정수를 하나씩 확인하면서 D를 포함하는지 센다.

C. 'B'에서 센걸 출력한다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private ArrayList<Integer> getPn(int a, int b) {
        boolean[] chk = new boolean[b+1];
        int sqrt = (int)Math.sqrt(b);
        for (int i = 3; i <= sqrt; i+=2) {
            if (chk[i]) continue;
            int base = i+i;
            while (base <= b) {
                chk[base] = true;
                base += i;
            }
        }

        ArrayList<Integer> pns = new ArrayList<>();
        if (a <= 2) pns.add(2);
        a = Math.max(a, 3);
        if ((a&1)==0) a++;
        for (int i = a; i <= b; i+=2) {
            if (!chk[i]) pns.add(i);
        }
        return pns;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        ArrayList<Integer> pns = getPn(a, b);
        int cnt = 0;
        for (int pn : pns) {
            while (pn != 0) {
                if (pn%10 == d) {
                    cnt++;
                    break;
                }
                pn/=10;
            }
        }

        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}