[Baekjoon] 5636_소수 부분 문자열

Silver I

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

---

< 소수 부분 문자열 >

 

문제 풀이 

 

2보다 크거나 같고, 100,000보다 작거나 같은 소수만 소수라고 했으므로 에라토스테네스의 체를 사용하여 100,000까지 소수 판별을 한다. 입력받은 문자열을 1자리부터 6자리까지 구할 수 있는 모든 부분 문자열을 구해 가장 큰 소수를 구한다.

 

 

 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 _5636_ { // 소수 부분 문자열

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

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

		String str = "";
		while (!(str = bf.readLine()).equals("0")) {
			int max = 0;
			for (int i = 0; i < str.length(); i++) {
				for (int j = i; j < i + 6; j++) {
					if (j >= str.length())
						break;
					int num = Integer.parseInt(str.substring(i, j + 1));
					if (num > 100000) {
						continue;
					}
					if (!arr[num]) {
						max = Math.max(num, max);
					}
				}
			}
			bw.write(max + "\n");
		}
		bw.flush();
	}
}

변수)
arr : 0~100,000 소수 판별
str : 입력받은 문자열
max : 가장 큰 소수 부분 문자열

 

에라토스테네스의 체 알고리즘을 사용하여 0부터 100,000까지 소수를 판별한다.

0이 아닐 때까지 문자열을 입력받아 다음 과정을 반복한다.

 

1) 100,000보다 작거나 같은 소수만 소수이므로 1자리~6자리의 부분 문자열을 구한다.

2) 부분 문자열을 구해 100,000보다 작거나 같다면 소수인지 판단한다. 소수라면 가장 큰 소수 부분 문자열인지 판단한다.

 

가장 큰 소수 부분 문자열을 출력한다.

---

---