파이썬으로 풀어보는 백준 2581번: 소수

https://www.acmicpc.net/problem/2581

2581번: 소수

 

내 풀이:

M=int(input())
N=int(input())
if M==1 and N==1:
    print("-1")
    exit()
prime=[2]
for i in range(3,N+1,2):
    j=0
    while True:
        try:
            if i%prime[j]==0:
                break
            else:
                j+=1
        except:
            prime.append(i)
            break
if max(prime)<M:
    print("-1")
    exit()
i=0
while True:
    if prime[i]>=M:
        break
    else:
        i+=1
min=i
sum=0
while True:
    try:
        sum+=prime[i]
        i+=1
    except:
        break
print(sum)
print(prime[min])

너무나도 복잡한 알고리즘. 최댓값 N에 따라서 10000까지의 소수를 찾을 필요는 없도록 만든 점에서는 만족한다.

 

registered님의 풀이:

arr = [False, False] + [True] * 9999
for i in range(2, 101):
    if arr[i]:
        for j in range(i * 2, len(arr), i):
            arr[j] = False
 
m = int(input())
n = int(input())
nums = [i for i in range(m, n+1) if arr[i]]
print(sum(nums)if len(nums) else -1)
print(min(nums) if len(nums) else '')

10001개의 성분을 갖는 list를 통해서 10000까지의 소수를 구분한다. 구분하는 방법은 2의 배수 제거, 3의 배수 제거, 4의 배수 제거, ..., 10000의 배수를 제거하는 방식이다. 10000까지의 소수를 미리 만든 후 M과 N을 입력한다.