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)
시간복잡도 :
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))))
에라토스테네스의 체
시간복잡도 :
(+) 위와 같은 방법으로 에라토테네스 체를 구현하면 느리다. 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