백준 2581 (python): 소수

import math

m = int(input())
n = int(input())

num = [True for i in range(10001)]
num[0] = False
num[1] = False

for i in range(2, int(math.sqrt(n))+1): # 어차피 약수는 대칭이므로 n의 제곱근까지만 확인
    if num[i] == True:
        j = 2
        while i * j <= n:
            num[i*j] = False
            j += 1
            
answer = []
for i in range(m, n+1):
    if num[i] == True:
        answer.append(i)
        
if len(answer) > 0:
    print(sum(answer))
    print(answer[0])
else:
    print(-1)

 

에라토스테네의 체.. 뭔 이름이 이따구?

원리는 다음과 같다

1. 2부터 N까지 존재하는 모든 자연수를 나열한다.
2. 나열된 숫자 중에서 가장 작은 수를 x로 지정한다.
3. 나열된 숫자 중에서 x의 배수를 모두 제거한다. (이때, x는 제거하지 않음)
4. 더 이상 반복할 수 없을 때까지 2번과 3번을 반복한다.

이렇게 해서 남은 것들은 소수이다!

 

+ 0, 1은 소수가 아니므로 따로 제외해주기

 

math.sqrt() 제곱근 구하기