[백준][Python] 9421번 소수상근수

9421번: 소수상근수

 

 

코드

import math
def prime(num):
	for i in range(2,int(math.sqrt(num))+1):
		if num % i == 0:
			return False
	return True
    
def check(num):
	visit = {}
	while 1:
		n = str(num)
		num = 0
		for i in range(len(n)):
			num += int(n[i]) ** 2
		if num == 1:
			return True

		if num in visit:
			return False
		else:
			visit[num] = 1
		
n = int(input())
for i in range(7,n+1):
	if prime(i):  # 소수인지 확인
		if check(i): # 상근수인지 확인
			print(i)

 

설명

숫자가 소수이면 check 함수를 통해 상근수인지 확인한다. 

각 자리의 수의 제곱을 더한 값을 구하기 위해서 숫자를 string형으로 변환을 해서 곱해주었다.

 

각 자리의 제곱을 더한 값이 다시 반복되어 나온다면 상근수가 될 수 없으므로 false를 return한다.

반복되는지 확인하기 위해 딕셔너리를 사용하였다.