[백준 / 정수론] 1978 : 소수 찾기 (python)

문제 설명

문제

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

입력

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

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

 

풀이

# 소수 찾기
# 에라토스테네스의 체

# n < 1,000 이하의 자연수
import math

n = int(input())
num = list(map(int, input().split()))
cnt = 0

A = [i for i in range(1001)]
A[1] = 0

for i in range(2, int(math.sqrt(len(A)) + 1)):
    if A[i] == 0:
        continue
    for j in range(i + i, len(A), i):
        A[j] = 0

for i in range(n):
    if A[num[i]] != 0:
        cnt += 1

print(cnt)

 

• 에라토스테네스의 체를 이용하여 소수를 구한다.
• 전체 수가 1,000 이하의 자연수이므로 소수를 찾기 위한 A 리스트 길이를 1001로 설정한다.
• A는 인덱스와 값이 동일하다.
• for문을 돌면서 소수를 판별한다. 소수일 경우 0으로 값을 할당한다.