[JAVA] 소수 사이 수열_3896

출처: https://www.acmicpc.net/problem/3896

3896번: 소수 사이 수열

 

 

 

소수 사이 수열 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

1903

1186

1003

64.336%

문제

연속한 소수 p와 p+n이 있을 때, 그 사이에 있는 n-1개의 합성수(소수나 1이 아닌 양의 정수)는 길이가 n인 소수 사이 수열라고 부른다.

양의 정수 k가 주어졌을 때, k를 포함하는 소수 사이 수열의 길이를 구하는 프로그램을 작성하시오. k를 포함하는 소수 사이 수열이 없을 때는 길이가 0이다.

예를 들어, 소수 23과 29의 소수 사이 수열은 {24, 25, 26, 27, 28}이고, 길이는 6이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 테스트 케이스는 한 줄로 이루어져 있고, 한 줄에 정수 k가 주어진다. 각각의 정수는 1보다 크고, 100000번째 소수(1299709)와 작거나 같다.

출력

각각의 테스트 케이스에 대해서 k가 합성수라면 k를 포함하는 소수 사이 수열의 길이를 출력한다. 그렇지 않으면 0을 출력한다.

예제 입력 1 복사

5
10
11
27
2
492170

예제 출력 1 복사

4
0
6
0
114

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2007 in Tokyo B번

• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: csh519
• 잘못된 번역을 찾은 사람: jh05013

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

 

 

 

 

---

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main
{
    private static Scanner s = new Scanner(System.in);
    
    public static void main(String[] args) {
    	
    	int T = s.nextInt(); // 테스트 케이스의 수
    	
    	int[] inputArray = new int[T];
    	int max = Integer.MIN_VALUE; // 최대값 별도 저장 (한 번에 찾기 위함)
    	for(int i=0; i<T; i++) {
    		inputArray[i] = s.nextInt();
    		
    		if(max < inputArray[i]) max = inputArray[i];
    	}
    	
    	Boolean[] dp = new Boolean[1299710];
    	dp[0] = true; // 0과 1은 소수가 아님.
    	dp[1] = true;
    	List<Integer> primeList = new LinkedList<>(); // 입력이 잦을 예정이므로 LinkedList 사용
    	
    	for(int i=2; i<1299710; i++) {
    		if(dp[i] != null && dp[i]) continue; // 소수가 아니면 PASS
    		primeList.add(i); // 소수는 저장
    		
    		for(int j=i; j<1299710; j+=i) {
    			dp[j] = true; // 소수의 배수는 소수가 아님.
    		}
    	}
    	
    	// LinkedList로 선언되었기에 빠른 검색을 위해 Array로 변환
    	int[] primeArray = new int[primeList.size()];
    	int count = 0;
    	for(int prime : primeList) {
    		primeArray[count++] = prime;
    	}
    	
    	StringBuffer result = new StringBuffer();
    	String LINE_SWAP="\n";
    	
    	for(int i=0; i<T; i++) {
    		for(int j=0; j<primeArray.length; j++) {
    			Boolean isFound = false;
    			
    			if(inputArray[i] == primeArray[j]) {
    				result.append("0");
    				isFound = true;
    			}
    			else if(inputArray[i] > primeArray[j] && inputArray[i] < primeArray[j+1]) {
    				result.append(primeArray[j+1] - primeArray[j]);
    				isFound = true;
    			}
    			else if(inputArray[i] < primeArray[j] && inputArray[i] > primeArray[j-1]) {
    				result.append(primeArray[j] - primeArray[j-1]);
    				isFound = true;
    			}
    			
    			if(isFound) {
    				if(i != T-1) {
    					result.append(LINE_SWAP);
    				}
    				break;
    			}
    		}
    	}
    	
    	System.out.println(result.toString());
    }
}