백준 알고리즘 2581 (소수) - python

[문제] 백준 알고리즘 2581 (소수) - python

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

2581번: 소수

 

1978번(소수 찾기)이랑 비슷한 문제이다.

다른 점은 배열이 주어지는 것이 아니라 범위가 주어지고, 

소수들의 합을 출력하거나 소수가 범위안에 없을 때는 -1을 출력하는 정도이다.

 

1978번 풀었을 때와 풀이 방법은 거의 같다.

1이 아닌 요소(i)를 하나씩 꺼내면서 2~ i-1까지 나눠지는 수가 없을 때만을 골라낸다.

나눠지는 수가 존재하면 더 이상 소수가 아니므로, 시간 낭비를 줄이기 위해 break 한다. 

플래그(check)를 이용하여 나눠지는 수가 있을 때만 출력용 배열에 append 하여 합과 첫 값을 출력하거나,

아무 것도 없을 때는 -1을 출력해주면 된다.

 

[Code]

M = int(input())
N = int(input())
prime = []
for i in range(M, N+1):
    if i != 1:
        check = True
        for j in range(2, i):
            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])