[백준] 9421 소수상근수

문제

---

양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다.

700은 상근수이다.

• 72 + 02 + 02 = 49
• 42 + 92 = 97
• 92 + 72 = 130
• 12 + 32 + 02 = 10
• 12 + 02 = 1

2는 상근수가 아니다.

• 22 = 4
• 42 = 16
• 12 + 62 = 37
• 32 + 72 = 58
• 52 + 82 = 89
• 82 + 92 = 145
• 12 + 42 + 52 = 42
• 42 + 22 = 20
• 22 + 02 = 4
• 42 = 16
• ... 끝나지 않는다

소수는 1과 자기자신을 제외하고 약수가 없는 수이다. 2, 3, 5, 7, 11, 13, 17, 19, ... 는 소수이다.

소수상근수는 소수이면서 상근수인 숫자이다. 7, 13, 19, ... 는 소수 상근수이다.

n이 주어졌을 때, n보다 작거나 같은 모든 소수상근수를 구하는 프로그램을 작성하시오.

 

 

 

 

 

풀이

---

 

우선 에라토스테네스의 체를 이용하여 소수를 찾아줍니다.

static void setPrimeNumber(int n) {
	primeNumber = new boolean[n + 1];
	
	for(int i = 2 ; i * i <= n ; i++) {
		if(primeNumber[i])
			continue;
		for(int j = i * i ; j <= n ; j += i) {
			primeNumber[j] = true;
		}
	}
	
	return;
}

 

위의 방식으로 소수를 찾아준 뒤 상근수를 찾아주면 된다.

 

상근수는 HashMap 과 HashSet을 이용하였는데.

 

HashMap 은 한번 상근수를 계산한 적이 있는 수를 다시 계산할 필요가 없게 하기 위해서 만들었다.

HashSet 은 상근수를 계산할 때 무한한 계산이 되는 것이기 때문에 한번 계산을 한 적 있는 수를 다시 들어왔을 때 반복문을 종료하기 위해서 선언하였다.

 

상근수를 찾는 코드는 아래와 같다.

static boolean findSolution(int n) {
	
	
	if(map.containsKey(n)) {
		return map.get(n);
	}
	
	int sum = 0;
	for(int i = n ; i > 0 ; i /= 10) {
		
		sum += Math.pow(i % 10, 2);
	}
	
	// 합이 1 이면 상근수 값을 map 에 추가하여 나중에 검색할때 찾기 편하게함
	if(sum == 1) {
		map.put(n, true);
		return true;
	}
	// 상근수가 아닐경우
	else {
		
		boolean result = false;
		// 이미 한번 왔던 숫자인지 판단하기 위해 set에 넣어줌
		if(set.contains(sum)) {
			result = false;
		}
		else {
			//한 번 들린 수 인지 판단하기 위해 set에 넣어준뒤 재귀적으로 검색을 함
			set.add(sum);
			result = findSolution(sum);
		}
		//만약 상근수인지 아닌지에 대해 나중에 반복 계산없이 판단하기 위해 map에 해당 값을 넣어줌
		map.put(n, result);
		
		return result;
	}
}

코드의 자세한 설명은 주석으로 남겨놓았다.

 

 

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static HashMap<Integer, Boolean> map;
	static HashSet<Integer> set;
	static boolean[] primeNumber;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bufferedReader.readLine());
		
		setPrimeNumber(n);
		
		map = new HashMap<>();
		for(int i = 2 ; i <= n ; i++) {
			if(!primeNumber[i]) {
				set = new HashSet<Integer>();
				if(findSolution(i)) {
					sb.append(i + "\n");
				}
			}
		}
		
		System.out.println(sb);
	}
	
	static void setPrimeNumber(int n) {
		primeNumber = new boolean[n + 1];
		
		for(int i = 2 ; i * i <= n ; i++) {
			if(primeNumber[i])
				continue;
			for(int j = i * i ; j <= n ; j += i) {
				primeNumber[j] = true;
			}
		}
		
		return;
	}
	
	static boolean findSolution(int n) {
		
		
		if(map.containsKey(n)) {
			return map.get(n);
		}
		
		int sum = 0;
		for(int i = n ; i > 0 ; i /= 10) {
			
			sum += Math.pow(i % 10, 2);
		}
		
		// 합이 1 이면 상근수 값을 map 에 추가하여 나중에 검색할때 찾기 편하게함
		if(sum == 1) {
			map.put(n, true);
			return true;
		}
		// 상근수가 아닐경우
		else {
			
			boolean result = false;
			// 이미 한번 왔던 숫자인지 판단하기 위해 set에 넣어줌
			if(set.contains(sum)) {
				result = false;
			}
			else {
				//한 번 들린 수 인지 판단하기 위해 set에 넣어준뒤 재귀적으로 검색을 함
				set.add(sum);
				result = findSolution(sum);
			}
			//만약 상근수인지 아닌지에 대해 나중에 반복 계산없이 판단하기 위해 map에 해당 값을 넣어줌
			map.put(n, result);
			
			return result;
		}
	}
}