소수 찾기 효율성

1. 에라토스테네스의 체 

2. 제곱근 만큼만 수행하면된다.

 

이 두 개를 합치면 소수 찾기 효율성 무적이 된다.

 

Solution

num = set(range(2, n+1))

for i in range(2, int(math.sqrt(n))+1):
	if i in num:
    	num-=set(range(i*2, n+1, i)

 

Reference

https://jungeun960.tistory.com/183

https://seongonion.tistory.com/43