2581 소수

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

"""
에라토스테네의 체를 이용하면 범위내에 있는 소수들을 빠르게 찾을 수 있다.

"""

def check_value(val):

    return

M = int(input())
N = int(input())

"""
M이상 N이하의 수들 중 소수를 찾기 위해
2부터 N까지의 수를 일단 나열해보자.
"""
from collections import deque

array = deque([i for i in range(2,N+1)])
# 에라토스테네스의 체는 다음과 같은 방식
# array에서 제일 작은 수부터 하나씩 꺼내서, 나눠지는 수들은 다 빼버린다.
# 그리고 현재 선택된 수를 저장한다.
# 나눠지는 수가 없더라도 그냥 저장한다.
# 저장된 수들이 소수들이다.

# 그렇다면 array를 queue로 만들면 편할 듯.
save_array = []
while array :
    now = array.popleft()
    temp_array = deque()
    for i in range(len(array)) :
        # 남은 array를 돌리면서 나눠지는게 있으면 pop상태로 두기
        temp = array.popleft()
        if temp % now == 0 :
            continue
        else :
            # 0이 아니라면 나눠지지 않는 것이므로 temp_array에 저장
            temp_array.append(temp)
    # array를 temp_array로 갱신
    # temp_array는 나눠지지 않은 목록들을 갖고 있다.
    array = temp_array
    if now >= M :
        save_array.append(now)
if len(save_array) == 0 :
    print(-1)
else :
    print(sum(save_array))
    print(min(save_array))

3. 풀이 및 생각

문제 풀이

소수를 이용한 문제는 다양한 풀이 방법이 있지만, 사실상 에라토스테네스의 체방법을 사용하는 것이 일반적이라고 하며, 가장 효율적인 듯 하다. 이 방법을 이용해서 문제를 풀면 되고, 단지 소수임을 확인하는 도중, M 이상인 값들만을 따로 저장토록하자.

나의 생각

에라토스테네스의 체에 대해 간단하게 설명하자면, 예를 들어 N까지의 모든 소수를 구하는 방식은 다음과 같다.

1. 2부터 N까지의 수를 list에 선언한다.
2. 제일 작은 값인 2를 x로 두고 x부터 끝까지 for문을 돌려서 list에 있는 나머지 값들을 전부 나눠보고 나눠지는게 있으면 제거한다.
3. 제거되지 않은 요소들 중에서 제일 작은 값을 x로 두고 2를 반복한다.

코드와 함께 본다면 금방 와닿는 알고리즘이며, 소수를 구할 땐 이 방식을 쓰도록 하자.