[백준/1978/파이썬(python3)] 소수 찾기

[백준/1978/파이썬(python3)] 소수 찾기

문제

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

입력

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

출력

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

입출력 예

입력	출력
4 1 3 5 7	3

풀이

def prime_list(n):
    n = n + 1 #추가된 부분
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i]:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i] == True]


testcase_count = int(input())
testcase_list = [int(i) for i in input().split()]
maxnumber = max(testcase_list)
primelist_of_max = prime_list(maxnumber)
count_of_prime_numbers = len(set(testcase_list) & set(primelist_of_max))

print(count_of_prime_numbers)

설명

일단 분류에 에라토스테네스의 체라고 써있는 걸 보긴 했는데 이게 뭔지 몰라서 해맸다. 위키에 검색해보니 아주 자세히 나와있을 뿐더러 python3로 구현된 함수까지 있었다. (위키백과-에라토스테네스의 체)

 이것을 이용하여 간단하게 구현하였다. 입력받은 값들에는 최대값이 있을 것이고, 해당 값을 기준으로 에라토스테네스의 체로 소수리스트를 만들었을 때, 입력받았던 숫자들 중에서 에라토스테네스의 체와 동일한 값만이 소수이므로 입력받은 숫자들과 에라토스테네스의 체에서 걸러진 소수리스트들의 교집합을 구하면 된다. 그 교집합 요소의 갯수가 이 문제에서 원하는 출력값이다.

 참고로 위키에서 제공한 함수는 주어진 값 '미만'의 소수리스트를 구하는 함수이다. 예제에서처럼 1 3 5 7을 입력하면 7미만의 소수 리스트, 곧 2, 3, 5만이 소수리스트로 반환된다. 이를 문제에서 사용하기 위해 내가 2번 라인에 임의로 n = n + 1이라는 코드를 삽입하였다. 만약에 이 함수를 사용할 생각이라면 이부분만 유의하면 될 것이다.