1978 소수찾기

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

from collections import deque

N = int(input())
array = list(map(int,input().split()))
temp_dict = {}
for j in array:
    temp_dict[j] = 1

arrange_list = deque([i for i in range(2,max(array)+1)])
save_list = []

while arrange_list :

    now = arrange_list.popleft()

    temp_list = []

    while arrange_list :
        check = arrange_list.popleft()
        if check % now != 0 :
            temp_list.append(check)
        else :
            continue
    arrange_list = deque(temp_list)

    # 여기까지 왔다는 것은 소수라는 것임
    if temp_dict.get(now) is not None :
        save_list.append(now)

print(len(save_list))

3. 풀이 및 생각

문제 풀이

에라토스테네의 체 방식을 이용하자. 현재의 수가 소수인지 아닌지 파악함과 동시에 dictionary 정보를 이용해서 빠르게 입력으로 받은 리스트에 들어있는 수인지 확인하자.

나의 생각

-