[Baekjoon] 9421_소수상근수

Silver I

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

---

< 소수상근수 >

 

문제 풀이 

 

먼저 값이 소수인지 판단 후 소수라면 상근수인지 판단한다.

 

 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;

public class _9421_ { // 소수상근수
	static Set<Integer> set = new HashSet<>();

	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 n = Integer.parseInt(bf.readLine());

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

		for (int i = 3; i <= n; i++) {
			if (!arr[i]) {
				set.clear();
				boolean result = check(i);
				if (result) {
					bw.write(i + "\n");
				}
			}
		}
		bw.flush();
	}

	private static boolean check(int i) {

		String num = Integer.toString(i);
		int answer = 0;
		for (int j = 0; j < num.length(); j++) {
			int temp = num.charAt(j) - '0';
			answer += (temp * temp);
		}

		if (i == 1) {
			return true;
		} else if (set.contains(answer)) {
			return false;
		}

		set.add(answer);
		return check(answer);
	}
}

변수)
n : 양의 정수
arr : 소수 판별
set : n의 각 자릿수의 제곱의 합 모음
answer : 각 자릿수의 제곱의 합

 

양의 정수 n을 입력받는다. n보다 작거나 같은 수 중에서 소수를 구한다. 소수라면 각 자릿수의 제곱의 합을 계산해 상근수인지 판단하기 위해 check 함수를 호출한다. 상근수라면 값을 출력한다.

 

check(int i)

각 자릿수의 제곱의 합을 구한다. 합이 1이라면 상근수 이므로 true를 반환한다. 만약 합이 set에 있는 값이라면(=이미 나온 적 있는 값이라면) 끝나지 않으므로 false를 반환한다. 둘 다 해당하지 않으면 set에 값을 추가하고 check함수를 다시 호출한다.

---

---