[BaekJoon] 3896 소수 사이 수열

1.  문제 링크

2.  문제

요약

• 연속한 소수 p와 p + n이 있을 때, 길이가 n인 소수 사이 수열이라는 것은 두 소수 사이에 있는 n - 1개의 합성수(소수나 1이 아닌 양의 정수)를 뜻합니다.
• 예를 들어 소수 31과 37 사이 수열은 {32, 33, 34, 35, 36}으로 길이가 6입니다.
• 양의 정수 k가 주어졌을 때 k를 포함하는 소수 사이 수열의 길이를 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어지고 그 다음 줄부터 T개의 줄에는 1보다 크고 1299709보다 작거나 같은 정수인 k들이 주어집니다.
• 출력: 각 테스트 케이스에 대해 k가 합성수라면 k를 포함하는 소수 사이 수열의 길이를 출력하고 k가 합성수가 아니라면 0을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public boolean isPrime(int num) {
		for(int i = 2; i <= Math.sqrt(num); i++) {
			if(num % i == 0) {
				return false;
			}
		}
		return true;
	}
	
	public int[] getPrimeLength(int[] primes) {
		int[] prime_length = new int[primes.length];
		for(int i = 0; i < primes.length; i++) {
			if(isPrime(primes[i])) {
				prime_length[i] = 0;
			} else {
				int count1 = 0;
				int count2 = 0;
				int upper = primes[i] + 1;
				int lower = primes[i] - 1;
				boolean flag1 = false;
				boolean flag2 = false;
				while(true) {
					if(!flag1) {
						if(isPrime(upper)) {
							flag1 = true;
						} else {
							count1++;
							upper++;
						}
					}
					if(!flag2) {
						if(isPrime(lower)) {
							flag2 = true;
						} else {
							count2++;
							lower--;
						}
					}
					if(flag1 && flag2) {
						prime_length[i] = count1 + count2 + 2;
						break;
					}
				}
			}
		}
		return prime_length;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		int[] primes = new int[num];
		for(int i = 0; i < primes.length; i++) {
			primes[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		int[] prime_length = m.getPrimeLength(primes);
		for(int i = 0; i < prime_length.length; i++) {
			bw.write(prime_length[i] + "\n");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 주어진 테스트 케이스가 소수라면 0을 출력하고 그렇지 않다면 해당 합성수부터 다음 소수까지의 합성수 개수와 해당 합성수부터 이전 소수까지의 합성수 개수를 구하여 두 소수 사이의 합성수 개수를 구하는 문제입니다.

1. 주어진 수가 소수인지 확인하고 소수라면 0을 출력합니다.

• 2부터 해당 수의 제곱근까지 해당 수를 나누어떨어지게 하는 수가 존재한다면 소수가 아닌 것이고 그렇지 않다면 소수인 것입니다.