[BAEKJOON] - 1456번 : 거의 소수

1456번 문제 링크

참고 포스팅

• https://velog.io/@osh8242/Java-1456%EB%B2%88.-%EA%B1%B0%EC%9D%98-%EC%86%8C%EC%88%98-%EC%86%8C%EC%88%98-%ED%8C%90%EC%A0%95

👀 정수론 문제

• 정수론은 시간 복잡도 보다는 해당 문제에 해당하는 알고리즘으로 접근이 가능한지 여부를 판단한 뒤 적용하는 문제일 경우가 다분합니다.
• 소수를 찾는 문제는 우선은 "에라토스테네스 체" 알고리즘을 통해 구현하면 됩니다.

📜 로직

• 이번 문제에서 주의할 사항은 "값의 범위" 입니다.
• 우선 A와 B가 10^14 이하이기 때문에, int 범위를 초과하게 되므로 long 자료형으로 선언해줘야 합니다.
• 이 후 에라토스테네스 체로 소수만 걸러냅니다.
• 그 다음 최댓값 보다 작은 제곱 수들을 카운팅(counting) 해줘야 합니다.
• 이 때, 거의 소수는 소수의 N(2 이상) 제곱이기 때문에 long 값을 초과하는 경우도 생각해야 합니다. 값을 곱하면 long의 범위를 넘어갈 수 있기 때문에 이항 정리로 처리해줘야 합니다.

while (temp <= (double) (b / i)) {
	if (temp >= (double) (a / i)) {
		answer++;
	}
	temp *= i;
}

기본적으로 temp * i <= b 와 같은 식으로 구현을 한 뒤 temp 값을 제곱하여 비교하지만, long 값의 범위 초과를 방지 하기 위해서 이항 정리하여 다른 형태로 구현하였습니다.( temp에 i를 곱해준 이유는 배열 크기 제한 때문에 Math.sqrt(b)를 해줬었기 때문입니다.)

😀 성공

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] s = br.readLine().split(" ");
        
        br.close();
        
        long a = Long.parseLong(s[0]);
        
        long b = Long.parseLong(s[1]);
        
        boolean[] isPrime = new boolean[(int)Math.sqrt(b) + 1];
        
        Arrays.fill(isPrime, true);
        
        isPrime[0] = isPrime[1] = false;
        
        for(int i = 2; i < isPrime.length; i++){
            if(!isPrime[i])
                continue;
            
            for(int j = i * 2; j < isPrime.length; j += i){
                isPrime[j] = false;
            }
        }
        
        int count = 0;
        
        for(int i = 2; i < isPrime.length; i++){
            
            if(isPrime[i]){
                
                long tmp = i;
                
                while(tmp <= (double)b/i){
                    
                    if(tmp >=(double)a/i){
                        count++;
                    }
                    
                    tmp *= i;
                    
                }
            }
        }
        
        System.out.println(count);
    }
}