[Baekjoon] 3896_소수 사이 수열

Silver I

문제(출처: https://www.acmicpc.net/problem/3896)

---

< 소수 사이 수열 >

 

문제 풀이 

 

먼저 에라토스테네스의 체를 사용하여 소수인지 아닌지 판단한다.

k를 입력받아 그 수가 합성수인지 먼저 판단 후 합성수라면 k를 포함하는 소수 사이 수열의 길이를 구한다.

 

 my solution (Java)

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

public class _3896_ { // 소수 사이 수열

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int t = Integer.parseInt(bf.readLine());

		boolean arr[] = new boolean[1299710];
		arr[0] = true;
		arr[1] = true;
		for (int i = 2; i < 649856; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 1299710; j += i) {
					arr[j] = true;
				}
			}
		}

		for (int i = 0; i < t; i++) {
			int k = Integer.parseInt(bf.readLine());

			if (!arr[k]) {
				bw.write(0 + "\n");
			} else {
				int cnt = 1;
				int num = k - 1;
				while (num>1 && arr[num--]) {
					cnt++;
				}
				num = k + 1;
				while (num<=1299710 && arr[num++]) {
					cnt++;
				}
				bw.write((cnt+1) + "\n");
			}
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 개수
arr : 소수 판단
k : 정수

 

테스트 케이스 개수 t를 입력받는다. 먼저 소수 판별을 쉽게 하기 위해 에라토스테스의 체를 사용하여 1부터 1299709까지 소수를 판별한다. 테스트 케이스 수만큼 정수 k를 입력받는다. 정수 k가 먼저 소수인지 합성수인지 판단한다. 소수라면 0을 출력한다. 소수가 아니라면 k보다 작은 수, 큰 수를 보면서 합성수의 개수를 구한다. k를 포함하는 소수 사이 수열의 길이를 출력한다.

---

---