2021.12.02

백준 2581 소수

#2581 소수

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

arr = [ i for i in range(M,N+1) if i > 1]   # M~N 까지 숫자 배열

for i in range(2, int(N**0.5)+1):       
    s = [i for i in range(0,N+1,i)]         # i의 배수 배열
    if i in arr:                            
        arr = list(set(arr) - set(s))       # arr에서 배수를 전부 빼고 
        arr.append(i)                       # 맨처음 숫자만 추가 
    else:
        arr = list(set(arr) - set(s))      

if arr == []:
    print(-1)
else:
    print(sum(arr))
    print(min(arr))

소수 문제를 해결할 때 에라토스테네스의 체를 사용하면 도움이 된다.

에라토스테네스의 체는 마치 체로 걸러내듯 소수를 찾는데

숫자 N까지의 소수를 찾고 싶으면 2부터 N까지의 숫자 배열을 작성하고

2부터 시작하여 2 이외의 2의 배수를 지운다. 2는 최초의 소수(p)

그리고 그다음 소수인 3을 제외한 3의 배수를 지운다. (p = 3)

이것을 p의 제곱이 N 보다 커질 때까지 계속한다.

이를 반대로 생각하여 N의 제곱근을 구하면 P의 최댓값 범위를 정할 수 있다.

range(2,int(N**0.5)+1)