[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부터 해당 수의 제곱근까지 해당 수를 나누어떨어지게 하는 수가 존재한다면 소수가 아닌 것이고 그렇지 않다면 소수인 것입니다.
2. 만약 소수가 아니라면 해당 수부터 1씩 증가시키며 증가시킨 수가 소수인지 확인하고 소수라면 해당 수가 소수임을 boolean 타입을 통해 표시하고 소수가 아니라면 해당 수보다 큰 수 중에서 합성수인 수의 개수를 1 늘려줍니다.
3. 2번 과정을 소수가 될 때까지 수를 1씩 증가시키며 반복합니다.
4. 2번 과정처럼 1씩 감소시키며 감소시킨 수가 소수인지 확인하고 소수라면 해당 수가 소수임을 boolean 타입을 통해 표시하고 소수가 아니라면 해당 수보다 작은 수 중에서 합성수인 수의 개수를 1 늘려줍니다.
5. 4번 과정을 소수가 될 때까지 수를 1씩 감소시키며 반복합니다.
6. 3, 5번 과정을 통해 두 수 모두 소수가 됐다면 해당 수보다 큰 수 중에서 합성수인 수의 개수와 해당 수보다 작은 수 중에서 합성수인 수의 개수를 더해주고 주어진 수 또한 합성수이기 때문에 1을 더해줍니다.
7. 두 소수 사이의 N - 1개의 수에 대해 길이가 N인 소수 사이 수열이라고 부르므로 7번 과정에서 더해준 수에 1을 더 더해줍니다.
8. 1번부터 7번 과정을 각 테스트 케이스에 대해 진행하고 각 테스트 케이스에 대한 결과를 출력합니다.