백준 1978번 소수 찾기

1. 문제 설명

문제링크

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

• 입력
  • 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
• 출력 :주어진 수들 중 소수의 개수를 출력한다.

2. 코드

import sys

input = sys.stdin.readline

# 1000 이하의 자연수 이다.
p = 10 ** 3

# 0, 1 은 소수가 아니므로 리스트 형태에서 False 표시 해준다.
# 이후 2 ~ 1000 까지 모든 숫자들은 True 표시 해둔다.
# 이때 p - 1 를 한 이유는 앞서 0, 1 의 길이 즉 2만큼 소수가 아님을 표시 해줬기 때문이다.
# 그래서 p - 1 의 길이 만큼만 True 표시를 해주면 길이는 1001 이다.
prime = [False, False] + [True] * (p - 1)

# 에라토스테네스의 체를 이용한 방식이다.
for i in range(1, p + 1):
    # 소수인지 판별!!
    if prime[i]:
        # 만약 i 가 소수라면 i의 배수들은 소수가 아님을 이용한 반복문이다.
        for j in range(2 * i, p + 1, i):
            prime[j] = False
# 판별한 숫자들의 갯수
n = int(input())

# 자연수들을 입력받는다.
numbers = list(map(int, input().split()))

# 소수가 몇개인지 카운트 하기 위한 변수
cnt = 0

# 반복문을 통해 각각 숫자들을 확인한다.
for num in numbers:
    # 만약 num이 소수 라면??
    if prime[num]:
        # 카운트 해준다.
        cnt += 1

# 출력
print(cnt)

3. 회고

Q. 문제를 보고 든 생각

• 소수인지 아닌지를 판별 해야할 자연수의 값 범위가 1000 이하 이지만, 속도 측면에 있어서 조금 더빠르게 하는 방식으로 코드를 작성 해보고 싶었다.
• 그래서 떠올린 방법은 에라토스테네스의 체 이다.
• 에라토스테네스의 체는 소수를 판별하는 알고리즘이고 단순하게 생각하여 소수의 배수는 소수가 아니다 라는것을 착안한 알고리즘 이라고 생각된다.

4. 고쳐야 할점

더 좋은 방법이 있다면 댓글로 알려주세요!!!