1부터 n의 sqrt2까지 소수인지 탐색 후 소수 리스트를 만들어 길이 반환
def solution(n):
nlist = [True] * (n+1)
m = int(n**0.5)
for i in range(2,m+1):
if nlist[i] == True:
for j in range(i+i,n+1,i):
nlist[j] == False
return len([i for i in range(2,n+1) if nlist[i] == True])
def solution(n):
num=set(range(2,n+1))
for i in range(2,n+1):
if i in num:
num-=set(range(2*i,n+1,i))
return len(num)
에라토스테네스의 체를 사용한 점에서 같은 알고리즘!
시간복잡도는 이 코드가 더 높을 것 같다.