[백준/파이썬] 9421번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 9421번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다.
700은 상근수이다.
-
72 + 02 + 02 = 49
-
42 + 92 = 97
-
92 + 72 = 130
-
12 + 32 + 02 = 10
-
12 + 02 = 1
2는 상근수가 아니다.
-
22 = 4
-
42 = 16
-
12 + 62 = 37
-
32 + 72 = 58
-
52 + 82 = 89
-
82 + 92 = 145
-
12 + 42 + 52 = 42
-
42 + 22 = 20
-
22 + 02 = 4
-
42 = 16
-
… 끝나지 않는다
소수는 1과 자기자신을 제외하고 약수가 없는 수이다. 2, 3, 5, 7, 11, 13, 17, 19, … 는 소수이다.
소수상근수는 소수이면서 상근수인 숫자이다. 7, 13, 19, … 는 소수 상근수이다.
n이 주어졌을 때, n보다 작거나 같은 모든 소수상근수를 구하는 프로그램을 작성하시오.
입력 요약
첫째 줄에 n (10 ≤ n ≤ 1000000)이 주어진다.
출력 요약
n보다 작거나 같은 소수상근수를 한 줄에 하나씩 오름차순으로 출력한다.
코드
n = int(input())
def prime_list(n):
sieve = [True] * n
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True:
for j in range(i+i, n, i):
sieve[j] = False
return [i for i in range(2, n) if sieve[i] == True]
pri = prime_list(n+1)
sp = set(pri)
sang = set()
for num in pri:
if num in sang :
continue
tmp = set()
tn = num
cnt = 0
while True:
tmp.add(tn)
tn = sum([int(i)**2 for i in list(str(tn))])
if tn == 1:
sang |= tmp & sp
break
if tn in tmp or cnt > 100:
break
cnt += 1
sang = list(sang)
sang.sort()
print("\n".join(map(str, sang)))
설명
핵심은 구현 관점에서 양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다.
700은 상근수이다.
-
72 + 02 + 02 = 49
-
42 + 92 = 97 …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기