1978 소수 찾기

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

#다이나믹 프로그래밍

1978번: 소수 찾기

#1978 소수 찾기

n=int(input())

#수의 개수 n

l=list(map(int,input().split()))

#int로 mapping해서 list로 만듬

dp=[1 for i in range(1001)]

#dp 생성
dp[1]=0
dp[0]=0

#0과 1은 소수가 아님

for i in range(2,33):

#여기서 고민을 좀 했는데 저게 최대이다 왜냐면 1000**(1/2) 가 31.6 머시기 이기 때문에 32부터는 j가 더 작아지게 되 #며 이 말인 즉슨 똑같은 수끼리 다시 곱해진다는 뜻 고로 32까지는 세주어야함 range니깐 33으로 설정

for j in range(i,501):

#i의 최소값인 2가 j와 만났을때 1000보다 작거나 같아야됨 최소값인 500 으로 설정 해야댐 range니깐 501로 설정

if i*j>1000:

#없어도 되긴한데 시간이 너무 길어진다
break
dp[i*j]=0

cnt=0

#카운트 생성

for i in l:

if dp[i]==1:

#위에 for문에서 살아남은 1들은 소수이다 "위에 for문은 1을 제외하고 서로서로 곱함으로써 소수가 아닌것들을 걸러내#는 장치였음

cnt+=1

print(cnt)

 

#원래 다이나믹 프로그래밍으로 하는게 아닌거 같은데 시간이 너무 오래걸리길래 dp로 만들어봤다.