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

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

9421번: 소수상근수

소수(prime)에 대해서 구현할 줄 알면 쉬운 문제였다.

'에라스토테네스의 체'를 이용하여 소수를 구하고 구현해주면 되는 문제였다.

에라스토테네스의 체 연습문제

 

재밌는점은 각 자리수를 제곱하고 더해주는 기법을 map()으로 표현할 수 있다는 점이다.

tmp = sum(map(lambda x: int(x) ** 2, temp))

map(적용시킬함수, 대상변수)

각 자리수에 대해서 int()와 제곱을 해주는 방식

num = int(input())

prime_num = []
prime = [True] * (num+1)

def isprime(n):
    n += 1
    for i in range(2, int(n ** 0.5) + 1):
        if prime[i]:
            for j in range(2 * i, n, i):
                prime[j] = False
    for i,value in enumerate(prime):
        if value:
            prime_num.append(i)
isprime(num)

ans=[]

for i in prime_num[2:]:
    visited = dict()
    temp = str(i)
    while True:
        tmp = sum(map(lambda x: int(x) ** 2, temp))
        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)