백준) 2581번 소수 문제 (파이썬)

문제) 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라

 

이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

 

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로,

 

이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

 

X = int(input())
Y = int(input())
arr = []

for i in range(X, Y+1):		# Y의 입력값을 포함하기 위해 +1을 함
    if i == 1:     # 1은 소수가 아니므로 pass
        pass
    elif i == 2:   # 2이면 리스트에 넣음 (2는 소수)
        arr.append(i)
    else:
        for j in range(2, i):
            if i % j == 0:     # 소수가 아니므로 break
                break
            elif j == i-1:	   # 소수이므로 리스트에 넣는다!
                arr.append(i)
if len(arr) == 0:  # 리스트가 없으면 -1로 출력
    print('-1')
else:
    print(sum(arr))
    print(min(arr))

이번 문제는 소수에 대한 알고리즘을 공부하였다.

 

더이상 나누어질 수 없는 수를 소수라고 하는데 일단 처음 1은 소수가 아니므로 제외를 하였고,

 

2는 소수기 때문에 처음 for문에 걸렀다.

 

이 후 2번째 for문에서 2부터 i 까지 반복하여 0으로 나누어 떨어지면 break하고,

 

j 가 i - 1과 동일하면 소수이므로 출력을 시켰다.  마지막 elif 의 패턴이 신기하였다.

 

어떤 수든 i - 1을 한 값이 j 와 같게 되면 소수인 것이다.

 

예를 들어 62를 i에 넣게 되면 61이 되는데 이것이 j (2 ~ 62) 반복되면 조건을 충족하는 61이 나오게 된다.

 

오늘 문제는 조금 어렵긴 했지만 나름대로 재미있었다.

 

이해가 안되시거나 틀린 정보는 댓글로 알려주시면 감사하겠습니다!