에라토스테네스의 체

이 알고리즘을 파이써닉하게 구현한 예제가 있길래 복습하고 싶은 마음에 글을 작성한다
단 하나의 숫자가 소수인지 아닌지 판별하는 용도로 사용하기 보다는 구간안에서 소수가 몇개인지
찾을 때 이용하면 성능이 좋다

set 활용

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)

평범한 반복으로 구현

def isPrime(n):
    nums = [0 for _ in range(n+1)]
    for i in range(2,n+1):
        for j in range(i+i,n+1,i):
            nums[j] = False
    
    for i in range(2, n+1):
        if n%i==0:
            return False

    return True