[백준 22788] Prime Digital Roots (JAVA)

https://www.acmicpc.net/problem/22788

22788번: Prime Digital Roots

 

 

이번 포스팅에서는 ICPC에서 출제 되었던 기출 문제를 한번 다뤄보도록 하겠다.

 

이 문제는 에라토스테네스의 체 알고리즘을 사용하면 간단히 해결이 가능하다.

 

에라토스테네스의 체는 하단 링크에 따로  정리해 두었으니 바로 문제분석으로 넘어가도록 하겠다.

 

 

https://0bliviat3.tistory.com/45

에라토스테네스의 체 (JAVA)

 

 

문제를 정리하자면,

 

주어지는 수를 차례로 소수인지 판별하고 소수가 아닌경우 각 자릿수의 합으로 소수인지 판별하길 반복하는 것이다.

이때 소수인경우는 해당 소수를 출력, 아닌경우는 none을 출력 해주면 된다.

 

 

그럼 에라토스테네스의 체를 사용해 구간내 모든 소수를 구해주도록 하겠다.

 

	static final int end = 1_000_000;
	static boolean[] primeArr = new boolean[end];
	
	static void eratos() {
		primeArr[0] = primeArr[1] = true;
		for(int i = 2; i*i < end; i++) {
			for(int j = i*i; j < end; j += i) {
				primeArr[j] = true;
			}
		}
	}

 

그리고 받은 입력값이 소수인지 확인하고 아니라면 각 자릿수를 더해 다시 재귀호출하는 메소드를 만들어주도록 하겠다.

 

 

	static int getRoot(int input) {
		if(!primeArr[input]) return input;
		if(input < 10) return 0;
		int sum = 0;
		for(int i = end/10; i > 0; i/=10) {
			int now = input/i;
			sum += now;
			input -= now*i;
		}
		return getRoot(sum);
	}

 

 

이제 남은 것은 출력형식에 맞춰 답을 내주면 된다.

이제 문제의 출력형식은 각 입력받은값과 판별한 값을 같이 출력하되,

각각의 자릿수를 7자리로 할당하고 오른쪽 정렬해 출력하도록 되어있으므로 String.format 을 사용해주도록 한다.

 

예제의 실행 결과는 다음과 같다.

 

 

아래는 코드의 전문이다.

 

package boj4;

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

public class Boj22788 {
	
	static final int end = 1_000_000;
	static boolean[] primeArr = new boolean[end];
	
	static void eratos() {
		primeArr[0] = primeArr[1] = true;
		for(int i = 2; i*i < end; i++) {
			for(int j = i*i; j < end; j += i) {
				primeArr[j] = true;
			}
		}
	}
	
	static int getRoot(int input) {
		if(!primeArr[input]) return input;
		if(input < 10) return 0;
		int sum = 0;
		for(int i = end/10; i > 0; i/=10) {
			int now = input/i;
			sum += now;
			input -= now*i;
		}
		return getRoot(sum);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		eratos();
		
		String now = in.readLine();
		
		while(!now.equals("0")) {
			sb.append(String.format("%7s", now)).append(' ');
			int root = getRoot(Integer.parseInt(now));
			if(root == 0) {
				sb.append(String.format("%7s", "none"));
			}else {
				sb.append(String.format("%7d", root));
			}
			sb.append('\n');
			now = in.readLine();
		}
		
		in.close();
		
		System.out.print(sb);
	}

}