[백준 9421] 소수상근수

 

n보다 작거나 같은 소수에 대해 문제의 로직을 통해 소수상근수를 구해야 한다.

2는 상근수가 아님을 알려주어서 3부터 n까지의 소수상근수 계산을 수행했다.

 

상근수가 아님을 알기위해 상근수 계산을 하며 구한값들을 집합에 담아 중복체크를 했다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        boolean prime[] = new boolean[1000001];
        for(int i=2; i<=1000000; i++)
            for(int j=i*2; j<=1000000; j+=i)
                prime[j] = true;
        
        for(int i=3; i<=n; i++) {
            if(!prime[i]) {
                Set<Integer> set = new HashSet<Integer>();
                String s = String.valueOf(i);
                boolean success = false;
                while(true) {
                    int sum = 0;
                    for(int j=0; j<s.length(); j++)
                        sum += Math.pow(s.charAt(j) - '0', 2);
                    if(sum == 1) {
                        success = true;
                        break;
                    }
                    if(!set.contains(sum)) {
                        set.add(sum);
                        s = String.valueOf(sum);
                    } else break;
                }
                if(success) System.out.println(i);
            }
        }
    }
}