[백준 2581] 소수 - python (solved.ac - 실버 5)

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

2581번: 소수

풀이

문제를 보았을때 알수있는 힌트

소수!-> 소수 문제는 에라토스테네스의 체 문제라는 것을 인지해두자

그냥 for문으로 풀면 시간초과가 나오니 에라토스테네스의 체로 소수를 찾고 문제를 풀면 쉽게 풀 수 잇는 문제이다.

M이상도 있고, 소수가 없는 경우는 첫째 줄에 -1을 나오게 하는 것만 고려해서 풀면 된다.

import sys

input = sys.stdin.readline

start=int(input())
end=int(input())
n_list=[False,False]+[True]*(end-1)
temp=[]

for i in range(2,end+1):
    if n_list[i]:
        temp.append(i)
        for j in range(2*i,end+1,i):
            n_list[j]=False
result=[]
for i in temp:
    if start<=i:
        result.append(i)
if len(result)==0:
    print(-1)
else:
    print(sum(result))
    print(result[0])

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2581.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리