9421 소수 상근수

각 자리의 숫자를 제곱해서 더한 후, 그 값이 1이 될 때 까지 반복해서
1이 되면 상근수, 그렇지못하고 무한루프를 돌게되면 상근수가 아니라고 할 때,
n 이하의 소수인 상근수를 모두 출력하는 문제이다.

이 문제를 풀기위해선 일단 소수를 걸러내야 한다.
일반적인 소수판별 알고리즘을 사용하면 O(n*root(n))의 시간으로 소수를 판별 가능하다.
이렇게 하면 풀리긴하지만 TLE인 1초에 매우 근접하게 된다.
여기선 에라토스테네스의 체를 통해 1부터 n까지의 소수를 미리 걸러내 주면
O(nlog(n)) 의 시간복잡도로 소수를 밝혀낼 수 있다.
둘다 별로 차이가 없어보일지 모르지만 이 문제에선 15배 더 빠른 결과를 보인다.

소수를 판별했으면, 상근수를 구해야 하는데, 이것도 모든 수를 일일히 구해볼 수는 없으므로
DP를 이용한다. 즉, 제곱해서 더한 수들이 이미 있으면 그 결과를 출력하고, 없으면 구해서 채워넣는 방식이다. 각 자리의 숫자를 구하는것을 반복하는것은 재귀를 이용했다.

소스