문제

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

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

아이디어

1. 주어진 수보다 작은 수로 모두 나눠서 1과 자기 자신의 수가 아닌수로 나눠지는 경우를 제외하고 개수를 센다.
2. 에라토스테네스의 체를 이용한다.

   100까지의 수 중에서 소수를 찾는다면,
   11^2>100이므로 모든 수로 다 나눌필요 없이 11보다 작은 수의 배수들만 지우면 된다.

   참고:https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

내 코드(Python) #error

num=int(input())
data=list(map(int,input().split()))
ans=0
for i in range(num):
    if data[i] != 1:
        for j in range(2,data[i]):
            if data[i]%j==0:
                break
            if j==data[i]-1:
                ans+=1
print(ans)

내 코드(Python) #1

num=int(input())
data=list(map(int,input().split()))
ans=0
for i in range(num):
    cnt=0
    if data[i] != 1:	#1은 소수가 아님
        for j in range(1,data[i]+1):	#1부터 자기 자신까지의 수로 나눔
            if data[i]%j==0:	#나눠지면 cnt+=1
                cnt+=1
        if cnt==2:	#1과 자기 자신의 수로 나눠진 경우(cnt==2)
            ans+=1
print(ans)

다른 코드(Python) #2 에라토스테네스의 체

import math

num=int(input())
data=list(map(int,input().split()))
num_list=list(range(2,1001))    #1은 소수가 아니므로 제외, 1000까지의 수
cnt=0

for i in range(2,math.ceil(math.sqrt(1000))):   #ceil = 올림
    for j in num_list:
        if j/i == 1:    #자신과 같으면 pass
            pass
        elif j%i==0:    #자신과 같지 않고 나눈 나머지가 0이면 소수가 아님
            num_list.remove(j)  #소수가 아닌 수는 제거
for k in data:
    if k in num_list:   #리스트에서 소수 찾기 
        cnt+=1
print(cnt)