[백준] 2581. 소수 - 파이썬

문제

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

2581번: 소수

설계

- 소수 : 1과 자기 자신으로만 나누어지는 수
- 2 ~ n-1 까지 모든 수로 나누어 판별 가능하지만 비효율적이다.
- 에라토스테네스의 체 : 제곱근까지만(가운데 약수까지만) 확인하면 된다

M = int(input())
N = int(input())
bucket = []

for i in range(M, N + 1):
    if i == 1:  # 예외처리 중요! 1일 경우 소수가 될 수 없다.
        continue
    n = (i ** (1/2)) // 1 + 1   # 제곱근까지만 소수를 확인한다.
    flag = 0
    for j in range(2, int(n)):
        if i % j == 0:
            flag = 1    # 소수가 아닐경우 flag on
            break
    if flag == 0:
        bucket.append(i)
if len(bucket) == 0:
    print(-1)
else:
    print(sum(bucket))	# 자동으로 처음 추가되는 수가 가장 작은 수 이다.
    print(bucket[0])