[python3] 1978번 소수 찾기

소수만 찾기에는 굉장히 어렵다. 그러면 어떻게 해야할까?

고대 그리스의 수학자인 에라토스테네스가 고안해낸 방법이 있다.

에라토스테네스의 체

1부터 N까지의 소수들을 찾아보자

1. 1을 제외한다. 1은 합성수도 소수도 아니다.

2. 2를 제외한 2의 배수를 모조리 지운다.

3. 3을 제외한 3의 배수를 모조리 지운다.

4. 4의 배수는 지울 필요가 없다. 2의 배수에서 이미 지워졌다.

5. N의 제곱근 이하의 소수까지 계속 해나간다.

6. 남은 숫자들이 소수이다.

단순히 말하자면 그냥 합성수를 모조리 지워버리면 된다.

import math

N = int(input())
num = input().split()
repeat = 2

num = [int (i) for i in num]
num.sort()
num.reverse()
mx = num[0]

root = math.sqrt(mx)

if num.count(1):
	num.insert(num.index(1), 0) 
	num.remove(1)
for Repeat in range(2, int(root+1)):
	while Repeat * repeat <= mx:
		if num.count(Repeat * repeat):
			num.insert(num.index(Repeat * repeat), 0) 
			num.remove(Repeat * repeat)
		repeat += 1
	repeat = 2
print(N-num.count(0))