[백준] 1978번 소수찾기 파이썬

문제

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

입력

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

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

문제풀이

• 에라토스테네스의 체로 문제 범위 1,000까지 소수를 모두 구한다.
• 위에서 계산한 리스트를 가지고 입력받은 리스트의 수로 인덱싱하여 해당 수를 리스트에 인덱싱한 값이 True면 answer에 저장한다.
• 최종으로 answer의 길이를 출력한다.

제출답안

import sys, math

input = sys.stdin.readline


def solution():
    range_number = 1000
    prime_array = [True for _ in range(range_number + 1)]
    for i in range(2, int(math.sqrt(range_number)) + 1):
        if prime_array[i]:
            j = 2
            while i * j <= range_number:
                prime_array[i * j] = False
                j += 1
    n = int(input())
    answer = []
    for i in list(map(int, input().split())):
        if i == 1:
            continue
        else:
            if prime_array[i]:
                answer.append(i)
    print(len(answer))

solution()