문제

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

입력

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

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

첫번째 풀이

N = input()
A = list(map(int, input().split()))

number = 0
for i in A:
    count = 0
    if i==1:
        continue
    for j in range(2, i+1):
        if i%j==0:
            count+=1
    if count == 1:
        number+=1

print(number)

comment

모든수를 나눌 필요는 없고 (i^0.5)+1까지 나눴을때 나눠지지 않는다면 이후에 약수는 없다.

두번째 풀이

N = int(input())
A = list(map(int, input().split()))

for i in A:
    if i==1:
        N-=1
    for j in range(2, int(i**0.5)+1):
        if i%j==0:
            N-=1
            break

print(N)