백준 2581 - 소수 (파이썬)

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

# 해결법

 

소수를 구하는 방법으로 유명한 에라토스테네스의 체를 구현해서 문제를 해결했다. 

소수를 의미하는 prime_number 리스트를 만들고 2에서 y까지의 모든 수를 넣는다.

그리고 2부터 y까지 반복문을 돌면서 i가 prime 리스트에 있다면 i를 제외한 i의 배수들을 모두 삭제한다.

그리고 최소값보다 큰 원소만 final_list에 넣고 final 리스트의 원소가 한개 이상이라면 원소들의 합과

최소 소수를 출력한다. 

그렇지 않을 경우는 -1 을 출력한다.

 

# 나의 코드

x = int(input())
y = int(input())
prime_number = list(range (2,y+1))
final_list = []
for i in range(2,y+1):
    if i in prime_number:
        for j in range(i+i, y+1, i):
            if j in prime_number:
                prime_number.remove(j)
for k in prime_number:
    if k >= x:
        final_list.append(k)
if len(final_list) > 0:
    print(sum(final_list))
    print(final_list[0])
else:
    print('-1')

이렇게 구현하니 통과되긴했지만 시간이 900ms 로 굉장히 오래걸렸다. 
그래서 시간을 더 줄일 방법이 없을까 고민하다, 2를 제외한 2의 배수를 모두 삭제하고 시작하면 시간이 더 많이 줄어들 것 같았다. 

3부터 2씩 더하면서 prime 리스트를 만들어줬기때문에 리스트의 맨 처음에 2를 따로 넣어줘야했다.

반복문을 돌면서도 in prime_number 로 조건을 설정하면 2의 배수를 모두 검색하기 때문에 in range(3, y+1, 2) 로 조건을 바꾸어주었다.

그리고 y보다 작거나 같을 경우 final 리스트에 더해지지 않도록 조건을 추가해줬다.

수정을 마치니 540ms로 대략 1.5배이상 속도가 빨라졌다.

 

# 개선 코드

x = int(input())
y = int(input())
prime_number = list(range (3,y+1,2))
prime_number.insert(0,2)
final_list = []
for i in range(3,y+1,2):
    if i in prime_number:
        for j in range(i+i, y+1, i):
            if j in prime_number:
                prime_number.remove(j)
for k in prime_number:
    if k >= x and k <= y:
        final_list.append(k)
if len(final_list) > 0:
    print(sum(final_list))
    print(final_list[0])
else:
    print('-1')