BOJ/백준-2581-python

문제📖

풀이🙏

• 입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.
• M은 N보다 작거나 같다.
• M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
• 단, M이상 N이하의 자연수 주 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
  -> 에라토스테네스의 체이론을 이용하여 구현하였다.

코드💻

# boj, 2581 : 소수, python3
# 수학, 정수론, 소수 판정
import sys

def eratos(s, n):
    sieve = [1] * (n + 1)

    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * 2, n + 1, i):
                sieve[j] = 0

    return [i for i in range(2, n + 1) if sieve[i] and i >= s]


def sosu(start, end):
    l = eratos(start, end)

    if len(l) == 0:
        return -1
    
    return '\n'.join(map(str, [sum(l), l[0]]))


if __name__ == '__main__':
    M = int(sys.stdin.readline())
    N = int(sys.stdin.readline())

    print(sosu(M, N))

결과😎

출처 && 깃허브📝

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