[ baekjoon ] 소수상근수 9421번 ( python )

문제

백준 9421 소수상근수 풀이 ( 파이썬 )

https://www.acmicpc.net/problem/9421

9421번: 소수상근수

 

풀이

지금까지 알고리즘 문제를 풀 때 소수 관련 풀이가 두 가지가 있었는데 이번 문제는 에라토스테네스의 체를 이용한 문제였다.

먼저 범위 안의 소수들을 primes에 넣고 이 소수들이 소수상근수인지 판별하여 확인했다.

소수상근수인지 확인할 때는 각 자리수의 곱을 더한 것이 또 나온다면 반복되는 것이므로 dict을 이용해 dict의 key가 존재한다면 반복되는 값이므로 멈춰서 해당하는 값은 정답에 넣지 않았다.

n=int(input())
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False

# print(primes)
ans=[]
for i in primes:
    visited=dict()
    temp=str(i)
    while True:
        tmp=sum(map(lambda x:int(x)**2,temp))
        # print(i,temp,tmp)
        idx=int(temp)
        if tmp==1:
            ans.append(i)
            break
        if visited.get(idx):
            break
        else:
            visited[idx]=1
        temp=str(tmp)

ans.sort()
for i in ans:
    print(i)