[백준 Java] 6219번 소수의 자격 (정수론)

💡문제

[Silver III] 소수의 자격 - 6219

문제 링크

성능 요약

메모리: 16376 KB, 시간: 148 ms

---

 

🤔접근법

범위 체크 및 시간복잡도 예상

• 범위 : 1 ≤ A ≤ B ≤ 4,000,000 , B ≤ A + 2,000,000
• 범위 순회 * 소수 판정
• $O(N^2)$은 최대 범위가 2백만이라 어렵다.
• $O(N\sqrt N)$도 1,000,000 * 1000 이라 어렵다 .
• $O(Nlog{N})$ 은 될 지 잘 모르겠다. 가능할듯 (대충 N * 8 정도 예상…)
• $O(\sqrt N)$ 또는 $O(Nlog{N})$ 이어야 한다.

풀이법

🅰️ 첫 번째 접근방법. 완탐 ⭕

1. 범위 A ~ B 까지 순회하면서 각 숫자들이 소수인지 판별
2. 소수이면 D를 포함하는지 판별
   ➡️ 해당 풀이법의 시간 복잡도 : $O(N\sqrt N)$

다만 소수 판별 경우 $O(N)$이면 시간초과니 $\sqrt N$까지만 탐색하여 $O(\sqrt N)$으로 줄이기로 하였다. 다시 생각해보니 이렇게 되면 $O(N\sqrt N)$이어서 초과가 날것 같다.

➡️ 해보니까 초과는 안나지만 느리긴 하더라..

위 방법은 패스

🅱️ 두 번째 접근 방법. 에라토스어쩌구 체 ⭕

1. 범위 A ~ B까지 에라토스테네스의 체 를 활용하여 소수 판별
2. 소수이면 D를 포함하는지 판별
   여기서 최악의 경우는 A = 2,000,000 , B = 4,000,000 이다.

• 에라토스테네스 체로 순회하며 소수판별 : 2,000,000 ($O(log(logN))$)
• 소수이면 숫자 판별 : 2,000,000 (N)
• D 포함 판별 : 7 (대략 10으로 잡자)

➡️ 해당 풀이법의 시간 복잡도 : $O(N+log(logN))$

코드에 따른 시간복잡도 설명은 아래에 👇

---

🤯FAIL

범위 오류

for (int i = 2; i <= B; i++) {
    if(!isPrime[i]) continue;
    if(A <= i && hasD(i)) {
        cnt++;
    }

    for (int j = i*i; j <= B ; j +=i) {
        isPrime[j] = false;
    }
}

처음에는 이렇게 코드를 짰다.

에라토스테네스의 체 로직과 함께 D를 가지고 있는지 판별하고 그 수의 배수를 false로 바꿔주는 형식이다.

이렇게 하게 되면 i 가 1,000,000이 되면 int 범위를 넘어가 j = i * i를 해줄 수 없기 때문에 최적화가 불가능하다.

범위를 잘 생각하자 … 다음과 같이 나눠 판별할 수 있도록 수정해주었다.

// 에라토스테네스의 체 (소수 판별)
for (int i = 2; i * i<= B; i++) { //log(log(n))
    if(!isPrime[i]) continue;
    for (int j = i*i; j <= B ; j += i) { //log(n)
        isPrime[j] = false;
    }
}

// D 숫자 포함 판별
for (int i = A; i <=B ; i++) { // n
    if(isPrime[i] && hasD(i)){
        cnt++;
    }
}

 

😎SUCCESS

생각한 시간복잡도와 로직은 맞게 판단하였다.

그.러.나

처음엔 완탐방법이 시간복잡도가 통과하지 못할 것으로 예상했는데 완탐으로 짠 코드가 있어서 해봤더니 통과하였다 .. 두둥 ~!

소수 판별하는 과정에서 2 ~ $\sqrt N$까지만 판별하게 되면 수가 작을 때는 더 작게 커도 2,000까지여서 그런지 통과가 가능하더라 …

+) 물론 N까지 돌고서 소수판별하게 되면 시간초과 난다.

---

👩‍💻 코드

// 첫 번째 접근방법. 완탐 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_6219 {
    static int A;
    static int B;
    static int D;

    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        for (int i = A; i<= B; i++) {
            if(isPrime(i) && hasD(i)){
                cnt++;
            }
        }

        System.out.println(cnt);

    }

    private static boolean hasD(int i) {
        while (i > 0){
            int n = i % 10;
            if(n == D){
                return true;
            }
            i /= 10;
        }
        return false;
    }

    private static boolean isPrime(int n) {
        if(n == 1) return false;
        for (int i = 2; i*i <= n; i++) {
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }

}

// 두번째 접근방법. 에라토스테네스의 체

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

public class Main_6219 {
    static int A;
    static int B;
    static int D;

    static boolean isPrime[];
    static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        isPrime = new boolean[4000001];

        Arrays.fill(isPrime, true);

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



        for (int i = 2; i * i<= B; i++) {
            if(!isPrime[i]) continue;
            for (int j = i*i; j <= B ; j += i) {
                isPrime[j] = false;
            }
        }

        for (int i = A; i <=B ; i++) {
            if(isPrime[i] && hasD(i)){
                cnt++;
            }
        }

        System.out.println(cnt);

    }

    private static boolean hasD(int i) {
        while (i > 0){
            int n = i % 10;
            if(n == D){
                return true;
            }
            i /= 10;
        }
        return false;
    }
}