백준 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보다 작거나 같은 모든 소수상근수를 구하는 프로그램을 작성하시오.

문제풀이

(1) 생각

 문제에 주어진 대로 각 자리수를 제곱하여 더하는걸 1이 될 때 까지 반복할 것입니다.
 이 과정 중, 반복되는 숫자가 나오면, 루프가 발생한 것이므로 해당 루프의 수들은 소수 상근수가 될 수 없습니다.
 문제 예시로 보면, 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 의 반복이 됩니다.
 따라서 4 이후 다시 16 -> 37 -> ... 이 반복 될 것이 자명하므로 이 루프 안의 8개의 수 4, 16, 37, 58, 89, 145, 42, 20 은 모두 소수 상근수를 만들 수 없게됩니다.

(2) 코드 8~9

 위 생각에 따라, 각 자리수 제곱합을 반복하는 과정에서 나오는 수들이, 소수 상근수를 만들 수 있는지, 없는지 여부를 기억하는 행렬을 만들어줍니다.

(3) 코드 39~47

 에라테네스의 체로 입력된 N 이하의 소수를 구하면서, 각 소수들이 소수상근수인지 판단해줍니다.

(4) 코드 10~34

 소수상근수 인지 판단해주는 함수를 만들어줍니다.
 각 자리수 제곱의 합이 1이 나오거나, 반복될 때까지 재귀적으로 반복하고, 각 과정의 수들을 set으로 저장해줍니다.
 과정이 끝나고, set에 저장한 과정들의 수들을 각각 소수상근수가 될 수 있는지, 없는지에 따라 (2)에 만들어 놓은 행렬에 저장합니다.