[BOJ] 백준 1456 거의 소수

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
	static List<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());
    	long b = Long.parseLong(st.nextToken());
    	int result = 0;
    	isPrime(10000000);
    	for(long p : list) {
    		for(long i=p;i<=b/p;i*=p) {
    			if(i*p >= a) result++;
    		}
    	}
    	System.out.println(result);
    }
    private static void isPrime(int n) {
    	boolean[] prime = new boolean[n+1];
    	Arrays.fill(prime,true);
    	prime[1] = false;
    	for(int i=2;i*i<=n;i++) {
    		if(!prime[i]) continue;
    		for(int j=i*i;j<=n;j+=i) {
    			prime[j] = false;
    		}
    	}
    	for(int i=2;i<=n;i++) {
    		if(prime[i]) list.add(i);
    	}
    }
}