[백준] 1978 소수 찾기

소수 찾기

• 티어 : Silver 4
• 시간 제한 : 2 초
• 메모리 제한 : 128 MB
• 알고리즘 분류 : 수학, 정수론, 소수 판정, 에라토스테네스의 체

문제

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

입력

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

출력

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

예제 입출력

---

Code

import sys
input = sys.stdin.readline

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

count_num = 0
for i in nums:
    count = 0
    if i < 4 and i > 1:
        count_num += 1
    else:
        for j in range(2, i//2 + 1):
            if i % j == 0:
                break
            else:
                count += 1
        if count == i//2 - 1:
            # print('i:', i)
            count_num += 1
        
print(count_num)

메모리: 30860 KB
시간: 72 ms