[알고리즘] 백준 9421 파이썬 - 소수상근수

 

9421번: 소수상근수

 

문제

양의 정수 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=int(input())
#01
x=[False,False]+([True]*(n-1))
for i in range(2,int(n**0.5)+1):
    for j in range(2*i,n+1,i):
        x[j]=False
#02
for i in range(2,n+1):
    if x[i]:
        tmp=[]
        z=i
        #03
        while True:
            sum=0
            for j in str(z):
                sum+=int(j)**2
            z=sum
            if(z in tmp):
                break
            if(z==1):
                print(i)
                break
            tmp.append(z)

- #01 : 입력받은 n까지 에라토스테네스의 체 사용

[알고리즘] 백준 17103 파이썬 - 골드바흐 파티션(에라토스테네스의 체)

- #02 : 2부터 n까지 소수인 경우만 빈 리스트 생성 후 z에 i값을 저장

- #03 : while문을 통해 각 자릿수의 제곱의 합을 sum에 저장 후 z에 sum을 저장

           만약 z가 tmp에 있다면 즉 소수상근수가 아니면 break한다.

           만약 z가 1 즉 소수상근수라면 i를 출력하고 break한다.

           둘 다 아니라면 tmp에 z를 추가한다.