백준 2581 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

쉽게 생각했다.

 

쉬운 건 맞다.

 

근데 오래 걸렸다.

 

코드부터 보자

 

코드

array = [1 for i in range(10002)]

array[:2] = 0, 0

for i in range(2,101):

    if array[i]:

        for j in range(i * i, 10001, i):

            array[j]= 0

n = int(input())

m = int(input())

a=0

for i in range(n,m+1):

    if array[i]:

        a += i

if sum(array[n:m+1]) > 0:

    print(a)

    print(array[n:m+1].index(1)+n)

else:

    print(-1)

시간제한이 1초 이기에, 범위값에서 하나씩 찾는 최악의 경우를 계산해 보니 느낌상 시간 초과가 될 것 같았다.

 

그래서 에라토스테네스의 체 방법으로 구해놓고 소수의 합을 구하도록 코드를 구현했다.