[백준 1456] 거의 소수

 

최근 한달동안 푼 문제중 가장 어려웠다;;;

 

1. 10^7 의 제곱은 10^14 이므로 10^7 보다 큰 수들은 소수 여부를 판별하지 않아도 된다.

int max = 10000000;
boolean prime[] = new boolean[max+1];

 

2. 2부터 B보다 작거나 같은 거의 소수들을 리스트에 담는다.

ArrayList<Long> list = new ArrayList<Long>();
for(int i=2; i<=max; i++) {
    if(b <= i) break;
    if(!prime[i]) {
        for(int j=2; true; j++) {
            if((long)Math.pow(i, j) > b) break;
            list.add((long)Math.pow(i, j));
        }
    }
}

 

3. 현재 리스트의 사이즈가 0 <= 거의 소수 <= B 의 개수이므로 A보다 같거나 작은 거의 소수의 개수를 빼준다.

   이분탐색으로 구했다.

int left = 0;
int right = list.size()-1;
while(left <= right) {
    int mid = (left + right)/2;
    if(list.get(mid) >= a) right = mid-1;
    else left = mid+1;
}

 

 

전체소스

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        int max = 10000000;
        
        boolean prime[] = new boolean[max+1];
        for(int i=2; i<=max; i++)
            for(int j=i*2; j<=max; j+=i)
                prime[j] = true;
        
        ArrayList<Long> list = new ArrayList<Long>();
        for(int i=2; i<=max; i++) {
            if(b <= i) break;
            if(!prime[i]) {
                for(int j=2; true; j++) {
                    if((long)Math.pow(i, j) > b) break;
                    list.add((long)Math.pow(i, j));
                }
            }
        }
        
        Collections.sort(list);
        int left = 0;
        int right = list.size()-1;
        while(left <= right) {
            int mid = (left + right)/2;
            if(list.get(mid) >= a) right = mid-1;
            else left = mid+1;
        }
        System.out.println(list.size() - left);
    }
}

 

데스크탑에서는 제한시간을 훌쩍 초과했는데 채점서버에 올리니 무난하게 통과했다.