행복한 소수

면접 대비

시간 제한1초메모리 제한256 MB

요약

n 이하의 수 중에서 소수이면서 자릿수 제곱합 반복이 1에 도달하는 수를 오름차순으로 한 줄에 하나씩 출력합니다.

문제

양의 정수 $n$ 의 각 자리 숫자를 제곱해서 모두 더한다. 그렇게 나온 합에도 같은 계산을 다시 한다. 이 과정을 반복하다가 1이 나오면 $n$ 을 행복수라고 한다.

700은 행복수이다.

2는 행복수가 아니다.

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

행복한 소수는 소수이면서 행복수인 수이다. 7, 13, 19, ...가 행복한 소수이다.

$n$ 이 주어지면 $n$ 보다 작거나 같은 행복한 소수를 모두 구하는 프로그램을 작성하시오.

첫째 줄에 $n$ 이 주어진다. ( $10 \le n \le 1\,000\,000$ )

$n$ 보다 작거나 같은 행복한 소수를 오름차순으로 한 줄에 하나씩 출력한다.