[백준] 1456번. 거의 소수(JAVA)

문제

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

---

풀이(38분)

import java.io.*;
import java.util.*;

public class Main {

    static boolean isPrime[] = new boolean[10000001]; // 문제에서 제시된 범위의 제곱근까지
    static ArrayList<Integer> list = new ArrayList<>(); // 소수를 저장할 리스트

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

        long a = Long.parseLong(st.nextToken()); // a 범위
        long b = Long.parseLong(st.nextToken()); // b 범위

        isPrime(); // 소수 판별
        
        int idx = 0; // 첫 소수 인덱스 
        long answer = 0; // 정답 추적

        while (idx < list.size() && list.get(idx) <= Math.sqrt(b)){ // 인덱스가 리스트 범위에 있고 && 제곱근을 초과하지 않았다면
            long mul = list.get(idx); // 곱해나갈 소숫값
            long num = mul; // 초기값
            boolean flag = false; // a보다 작은지
            if(num < a){ // 만약 초기값이 a보다 작다면
                flag = true; // 시작할 때 mul로 한번 나누고 시작
            }
            while(num < a){
                num *= mul;
            }
            if(flag) num /= mul;
            while (num <= b / mul) {  // 오버플로우 방지 검사 
                answer++;
                num *= mul;
            }
            idx++;
        }

        System.out.println(answer);
    }

    public static void isPrime(){ // 에라토스테네스의 체
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for(int i = 2; i < isPrime.length; i++){
            if(isPrime[i]){
                list.add(i);
                for(long j = i * (long)i; j < isPrime.length; j += i){
                    isPrime[(int) j] = false;
                }
            }
        }
    }
}

---

문제 풀이 전략

 

먼저 b의 최대 범위가 10^14까지인 매우 큰 수이기 때문에 제곱근인 10^7까지만 범위를 정해 판독한다.

 

10^7까지의 소수를 구해두고 다음과 같은 과정을 통해 진행한다.

 

1. 리스트 안에 있고, b의 제곱근보다 작은지 확인한다.(b의 제곱근보다 크다면 반드시 답이 되지 못한다.)

 

2. 곱해나갈 소수의 값을 정하고, 초기값을 소수의 값으로 한다.

2-1. 만약 초기값이 a보다 작다면 flag를 true로 해주고, a보다 커질 때까지 mul을 곱해나간다.

2-2. flag를 설정해 주는 이유는 a보다 작아 이미 제곱 연산이 진행된 값이라면 초기에 한번 mul을 나눈 뒤 값을 계산하기 위해서이다.

-> 이렇게 하지 않으면 a = 6, b =10 경우 2의 세제곱근인 8부터 진행이 되어야 한다. 하지만 num = 8이 되고, b / mul에서 잡히게 될 수 있는 것이다. 따라서 한 번 mul을 나누어주어야 한다.

2-3. num이 정해졌다면 num <= b / mul인 경우에 반복문을 진행해 준다.

-> 이 부분이 매우 중요하다.

-> 만약 num <=  b / mul이 아니라 num * mul <= b로 진행하면 어떻게 될까?

-> 소수라는 것을 빼고 생각하면 num = 10^7이 최댓값이다. 그렇다면 num * mul이 10^14인 경우 b 이하 연산을 통과하게 된다.

-> 하지만 다음 루프에 num *= mul을 통해 num = 10^14가 될 것이다.

-> 10^14 * 10^7을 하게 된다면 10^21 이 되어 b 이하 조건에서 걸리게 될 것이다!

-> 하지만 실제로는 오버플로우가 발생하여 b 이하 조건을 통과하는 경우가 존재한다.

---> 그렇기에 num * mul을 하는 것이 아니라 오버플로우가 발생할 일이 없는 b / mul 연산이 안전하다.

 

위의 2-3 과정 때문에 고민이 많았던 문제였다.

하지만 실제로 생각해 보면 습관적으로 num * mul을 했을 뿐이지 오버플로우를 염두에 둔다면 매우 안전하지 않은 연산이라는 것을 알 수 있었던 좋은 문제라고 생각한다.