백준 9421 자바 - 소수상근수 (BOJ 9421 JAVA)

문제 : https://www.acmicpc.net/problem/9421

 

일단 이 문제를 풀기 위해 필요한 부분을 살펴보자.

 

1. 1000000이하의 모든 소수를 알 수 있어야 한다.

-> 소수판정의 경우 간단히 에라토스테네스의 체를 사용해서 100만 이하의 모든 수에 대해 미리 소수를 구해두면 된다.

 

2. 상근수를 구할 수 있어야 한다. 이 때 '1'이 아예 안나오는 경우가 존재하므로 무한루프로 빠지지 않도록 하는 로직이 필요하다.

-> 1이 나오거나, 이미 나왔던 수가 다시 나올 때 까지(순환) '각 자리수의 제곱의 합'을 구해준다.

 

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/09400/BOJ_9421.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;

public class Main {
    ArrayList<Integer> list = new ArrayList<>();

    private void initPn(int n) {
        boolean[] pn = new boolean[n+1];
        for (int i = 2; i <= Math.sqrt(n); i++) {
            int base = i+i;
            while (base <= n) {
                pn[base] = true;
                base += i;
            }
        }
        for (int i = 2; i <= n; i++) {
            if (!pn[i]) list.add(i);
        }
    }

    private int proc(int num) {
        int sum = 0;
        while (num!=0) {
            int digit = num%10;
            num/=10;
            sum += digit*digit;
        }
        return sum;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        initPn(n);
        StringBuilder answer = new StringBuilder();
        for (int pn : list) {
            int def = pn;
            HashSet<Integer> hs = new HashSet<>();
            do {
                hs.add(pn);
                pn = proc(pn);
            } while (!hs.contains(pn) && pn!=1);
            if (pn == 1)
                answer.append(def).append('\n');
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}