2581 소수

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

#다이나믹 프로그래밍

2581번: 소수

#2581 소수 정리

m=int(input())
n=int(input())

#줄로 구분된 m,n 입력

dp=[1 for i in range(10001)]
dp[0],dp[1]=0,0

#dp생성 0 과 1은 즉 인덱스 0 과 1 은 0(소수가 아님)
sum_answer=0
min_answer=0

#변수 생성

for i in range(2,101):
for j in range(i,5001):
if i*j>10000:
break
if dp[i*j]==1:
dp[i*j]=0

#에라토스테네스의 체를 이용하여 문제 내의 dp의 한계인 10000까지 소수판정을 함

for i in range(m,n+1):
if dp[i]==1:
if min_answer==0:
min_answer=i
sum_answer+=i

#오름차순으로 정렬되어있기때문에 변수 min_answer가 처음이라면 최솟값인것이므로 i를 입력 그와 관계 없이 sum_answer에는 소수라고 판정된 i를 전부 합쳐준다
if min_answer:
print(sum_answer)
print(min_answer)
else:
print(-1)

#min_answer가 존재하지않으면 소수인것이 없는것

 

#중간에 헷갈렸던것은 에라토스 테네스의 체를 사용할때 i+1이냐 i이냐를 생각하는 것이였다. 3*3같은 것은 i+1이면 판정을 못하는데 그것을 생각하지 못해서 일어난 일이다..;