백준 python 문제풀이 - 소수(2581)

백준 문제 - 소수(2581)

 

[문제 간단 설명]

M과 N 사이의 수 중에서 소수만을 골라 합을 구하고, 최솟값을 구하는 문제이다.

 

[문제 풀이 핵심]

1. 두 숫자의 사이의 범위를 지정해야 한다.

2. 소수를 구해야 한다.

3. 소수 모임의 합을 구하고, 최솟값을 호출해야 한다.

 

[문제 풀이 과정]

1. for 문을 사용해 두 숫자 사이의 범위를 반복하게 제작.

2. 소수의 조건인 1과 자기 자신을 제외하고 약수는 없다는 점을 이용.

3. 구한 값을 리스트로 따로 모아 파이썬 내장 함수인 sum을 이용해 합을 구함.

4. 최솟값은 처음으로 입력된 리스트 값이므로 단순하게 0번을 호출함.

 

[소스 코드]

import sys

M = int(sys.stdin.readline())
N = int(sys.stdin.readline())

demicial_list = [] # 소수를 저장하는 리스트

for i in range(M, N+1): # 이하이므로 끝은 +1 처리를 해줌
    measure_list = [] # 약수를 모으는 함수
    for j in range(1, i): #1~i의 사이에 있는 숫자.
        if i % j == 0:
            measure_list.append(j)
    if len(measure_list) == 1:
        demicial_list.append(i)
if demicial_list: # 만약 소수가 존재한다면
    demicial_sum = sum(demicial_list)
    print(demicial_sum)
    print(demicial_list[0])
else:
    print(-1)

 

[개선 사항]

무식하게 모든 수를 계산하는 방식이므로 시간이 생각보다 오래 걸림.

숫자 범위에서 약수가 1개라도 있으면 그 수는 소수가 아니니 다음으로 건너뛰는 방식을 사용하면, 시간을 획기적으로 줄일 수 있음.