[백준 3896] 소수 사이 수열

 

에라토스테네스의 체 방법으로 소수 배열을 구해놓고

합성수 k 에 대해

 

k보다 크면서 가장 가까운 소수 - k보다 작으면서 가장 가까운 소수를 구한다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        boolean prime[] = new boolean[1299710];
        for(int i=2; i<1299710; i++)
            for(int j=i; i*j>2 && i*j<1299710; j++)
                prime[i*j] = true;
        
        int t = sc.nextInt();
        while(t-->0) {
            int k = sc.nextInt();
            if(prime[k]) {
                int s = k;
                int e = k;
                while(true) {
                    if(!prime[--s]) break;
                }
                while(true) {
                    if(!prime[++e]) break;
                }
                System.out.println(e-s);
            } else System.out.println(0);
        }
    }
}