[Baekjoon] 10434_행복한 소수

Silver II

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

---

< 행복한 소수 >

 

문제 풀이 

 

에라토스테네스의 체 알고리즘을 사용하여 소수를 먼저 구한다. 입력받은 정수를 소수인지 판단 후 소수라면 행복한 수인지를 판단한다. 

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class _10434_ { // 행복한 소수
	static Set<Integer> set;

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

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

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

		set = new HashSet<>();
		for (int i = 0; i < p; i++) {
			st = new StringTokenizer(bf.readLine());
			int t = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			if (arr[m]) {
				bw.write(t + " " + m + " NO\n");
			} else {
				set.add(m);
				check(Integer.toString(m));

				if (set.contains(1)) {
					bw.write(t + " " + m + " YES\n");
				} else {
					bw.write(t + " " + m + " NO\n");
				}
				set.clear();
			}
		}
		bw.flush();
	}

	private static void check(String m) {
		int sum = 0;
		for (int i = 0; i < m.length(); i++) {
			int x = m.charAt(i) - '0';
			sum += (x * x);
		}
		if (set.contains(sum)) {
			return;
		}
		set.add(sum);
		if(sum==1) {
			return;
		}
		check(Integer.toString(sum));
	}
}

변수)
p : 테스트 케이스 수
arr : 소수 판별
set : 자릿수의 제곱의 합 저장
t, m : 테스트 케이스 번호, 정수 M

 

테스트 케이스 수를 입력받는다. 먼저 소수를 판별하기 위해 에라토스테네스의 체 알고리즘을 사용하여 소수인지를 미리 구해둔다. 테스트 케이스 수만큼 다음 과정을 반복한다.

1) 테스트 케이스 번호, 정수 m 입력

2) m이 소수가 아니라면 NO 출력

3) m이 소수라면 set에 저장 후 check함수 호출

4) set에 1이 포함되어 있으면 행복한 소수이므로 YES 출력, 1이 포함되어 있지 않으면 NO 출력

 

check(String m)

각 자릿수의 제곱의 합을 구한다. 합이 이미 set에 포함되어 있는 수라면 사이클이 형성된 것이므로 종료한다. set에 포함되어 있지 않은 수라면 set에 저장한다. 만약 그 값이 1이라면 행복한 수이므로 종료한다. 1이 아니라면 check함수를 다시 호출한다.

---

---