에라토스테네스의 체 (소수 응용)

기존의 소수 문제보다 시간 단축이 엄청 됨

 

x이하의 소수 출력하기

import math
def prime_num(x):
    sieve=[True]*(x+1)
    for i in range(2,int(math.sqrt(x))+1):
        if sieve[i]==True:
            for j in range(2*i,x+1,i):
                sieve[j]=False

		return [i for i in range(2,x+1) if sieve[i]==True and i!=1]