[Python] 백준 2581번: 소수

www.acmicpc.net/problem/2581

import sys
input = sys.stdin.readline


def isPrimeNumber(n):
    for i in range(2, int(n**(1/2))+1):
        if n % i == 0:
            return False
    return True


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

isPrimeNumberList = [True]*(N+1)

primeMin = 10001
primeSum = 0

for i in range(2, N+1):
    if isPrimeNumberList[i]:
        if not isPrimeNumber(i):
            isPrimeNumberList[i] = False
            continue

        isPrimeNumberList[i] = True

        if i >= M:
            primeSum += i
            primeMin = min(primeMin, i)

        j = 2
        while i*j < N+1:
            isPrimeNumberList[i*j] = False
            j += 1

if primeMin == 10001 and primeSum == 0:
    print(-1)
else:
    print(primeSum)
    print(primeMin)

에라토스테네스의 채를 이용한다.

isPrimeNumberList[i]에 i라는 숫자가 소수인지 판별할 수 있도록 True/False를 저장한다. 우선은 모두 True로 초기화를 하고 for문을 시작한다. 만약 isPrimeNumberList의 값이 True여서 if문을 뚫었다면 정말 소수인지를 isPrimeNumber() 함수를 통해 확인한다. 소수가 아니라면 False를 주고 컨티뉴 한다. 소수가 맞을 경우에는, True를 주고, 이 문제에서 구하고자 하는 primeSum, primeMin의 값을 변경한다.(여기서 if i >= M이 붙은 것은, for문에서 i가 M~N이 아니라 2~N의 범위를 가지고 있기 때문이다.) 그리고 j를 이용한 while문이 에라토스테네스의 채의 핵심인데, 현재 숫자가 소수(가령 7)이므로, 그것의 배수(14, 21, ...)는 모두 소수가 아니다. 따라서 주어진 범위 내에서의 모든 배수에 대해 False를 준다.