백준 - (# 1978)

https://www.acmicpc.net/problem/1978

Code 1

from math import sqrt
N = int(input())
number_list = list(map(int, input().split()))

cnt = 0
for num in number_list:
    adder = 1

    for i in range(2,int(sqrt(num))+1):
        if num % i == 0:
            adder = 0
            break

    if num == 1:
        adder = 0

    cnt += adder

print(cnt)

시간복잡도 : $O(N^{\frac{1}{2}})$

Code 2

N = int(input())
number_list = list(map(int, input().split()))
max_num = max(number_list)
total_num_list = [x for x in range(2,max_num+1)]
prime_num_list = []

while total_num_list :
    p = total_num_list[0]
    prime_num_list.append(p)
    for mul_p in range(p,max_num+1,p):
        try :
            total_num_list.remove(mul_p)
        except:
            pass

print(len(list(set(number_list).intersection(prime_num_list))))

에라토스테네스의 체
시간복잡도 : $O(NloglogN)$

(+) 위와 같은 방법으로 에라토테네스 체를 구현하면 느리다. remove()때문인 듯 하다. 아래와 같이 boolean으로 구현하는 것이 효율적이다.

max_num = 1000000
total_num_list = [False, False] + [True]*max_num

for i in range(2,len(total_num_list)):
    if total_num_list[i] == True:
        for j in range(i + i, len(total_num_list), i):
            total_num_list[j] = False