[백준] 소수상근수(9421)

문제 링크 : [백준] 소수상근수(9421)

문제 설명

상근수 : 각 자리의 수를 제곱하여 더한 값이 1이면, 상근수, 아닌 경우, 앞의 행위를 계속 반복(1이 아닌 값에서 싸이클이 발생할 경우 상근수 아님)
소수상근수 : 상근수중 소수인 수
n이 주어질 때, n보다 작거나 같은 수 중, 모든 소수상근수를 출력하세요.

입력

N(1 <= N <= 1,000,000)

20

출력

7
13
19

카테고리

#에라토스테네스 #DP

시간 복잡도 상한

O(NlogN)

해결 방법

1. 에라토스테네스의 체를 이용하여 소수들을 구합니다.
2. 구해진 소수들 중, 상근수를 찾습니다.
   2-1. 각 자리수들을 제곱하여 더합니다.
   2-2. 그 수가 이전에 나오지 않았다면, 그 수를 기저조건에 맞지 않는 동안 반복합니다.
3. 기저조건은 아래와 같습니다.
   3-1. 수가 1인 경우, 소수상근수
   3-2. 이전에 소수상근수로 판명된 경우, 소수상근수
   3-3. 이전에 소수상근수가 아닌 수로판명된 경우, 소수상근수
   3-4. 아직 소수상근수인지 판명되지 않은 수 중, 이전에 방문했던 적이 있는 경우(싸이클이 발생한 경우)
4. 각 수에 대해 위 절차를 통하여 소수상근수인 경우에 그 수를 출력합니다.

시간복잡도

조금 애매하네요...

코드

#include<cstdio>
int n,i,j,d[1000001],v[487];
int r(int x){
    int p=0,t=x;
    while(t)p+=(t%10)*(t%10),t/=10;
    if(v[p])return v[p]=v[p]==1?1:2;
    v[p]=3;
    return v[p]=p==1?1:r(p);
}
int main(){
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        if(d[i])continue;
        for(j=2;j*i<=n;j++)d[i*j]=1;
        if(r(i)==1)printf("%d\n",i);
    }
}