<백준 문제풀이: 2581번> 소수

백준 1978번과 비슷한 소수 찾는 문제이다.

1. 방식 - (1)

우선 내가 풀려고 했던 방식을 한번 보자:

import sys

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

all_num = [x for x in range(M, N+1)]

for i in range(2, int((N+1)/2)):
    for j in range(len(all_num)):
        if all_num[j]%i == 0 and all_num[j] != i:
            all_num[j] = 0

prime_list = [x for x in range(M, N+1) if x in list(set(all_num))]
if len(prime_list) == 0:
    print(-1)
else:
    print('%d\n%d' %(sum(prime_list), min(prime_list)))

일단 답을 말하자면, 답은 맞으나 시간초과가 뜬다 이렇게 하는 것이 꼭 틀린 것은 아니지만 걸리는 시간이 너무 오래 걸려서 시간 초과가 뜬다.

1. all_num 리스트에 M부터 N까지의 숫자들을 정의한다.
   
2. 그리고 range(2, int((N+1)/2)) 에서 all_num[j]%i == 0 and all_num[j] != i 가 맞다면 (즉 i로 나누어 떨어지고, i가 아닌 all_num의 요소들) 이 요소들은 0으로 정의해준다. 즉, 소수가 아닌 숫자들은 0으로 정의해주는 것이다.
   
3. prime_list는 M과 N 사이의 숫자들을 찾아서 이 all_num 리스트에 있다면 추가해준다.
   
4. 마지막으로 문제가 요구하는 출력 방식에 맞게 정의해준다.
   

하지만 이렇게 하면 시간초과가 뜨므로, 다른 방식을 적용시켜줘야 한다.

2. 방식 - (2)

다음은 내가 정답으로 제출한 방식이다:

import sys

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

num = set(range(2, N+1))
for i in range(2, N+1):
    if i in num:
        num -= set(range(2*i, N+1, i))

prime_list = [x for x in range(M, N+1) if x in num]

if len(prime_list) == 0:
    print(-1)
else:
    print(sum(prime_list))
    print(min(prime_list))

여기서는 set를 이용하여 소수를 찾아주었다. 또한, 범위도 2부터 N까지에서의 i를 정의해주어, i가 만약 num 셋에 있다면, num 셋에서 set(range(2*i, N+1, i)), 즉 2*i 부터 N+1까지의 범위에서 i만큼의 간격을 둔 숫자들, 을 제외시켜준다. 이를 계속 반복하면 num 셋에서는 오직 소수들만 남아 있을 것이다.
그 다음, prime_list는 M부터 N까지의 숫자들 중 num 셋에 있는 숫자들로 정의해준다. 마지막에는 문제가 요구하는 출력 방식에 맞게 출력해준다.

3. 방식 - (3)

다음은 다른 사람이 푼 방식에 대해서 알아보겠다:

M = int(input())
N = int(input())
prime = []
for i in range(M, N+1): --- (1)
    if i != 1:
        check = True
        for j in range(2, i): --- (2)
            if i % j == 0:
                check = False
                break
        if check:
            prime.append(i)
if len(prime) == 0:
    print(-1)
else:
    print(sum(prime))
    print(prime[0])

이 풀이 방법은, 비슷한, check=True라는 변수를 정의해주고, 만약 range(2, i)에서 i%j == 0, 즉 나누어 떨어진다면, check=False라고 정의하고 바로 break를 하여 (2) for문을 탈출해준다. 만약 (2) for문에서 나누어 떨어지는 숫자가 없다면, 소수이므로, prime 리스트에 추가해준다. 마지막으로, 문제가 요구하는 출력 방식에 맞게 출력해주었다.

이렇게 보듯 소수 문제의 요지는 에라토스테네스의 체에 기반하여 푸는 것이 일반적이다. 하지만 더 효율적이냐 아니느냐가 시간초과를 야기하냐 마냐의 관건인 것을 알 수 있다. 다음은 내가 푸는데 얼마나 힘들었는지 보여주는 사진이다:

생각보다 많은 시도 끝에 푼 문제라 더 뿌듯한 것 같다