소수를 구하는 방법

1. 2이상 n이하의 수를 모두 쓴다
2. 가장 앞의 2를 제외한 2의 배수를 모두 지운다
3. 그다음 앞에 있는 3을 제외한 3의 배수를 모두 지운다
4. 위 행동을 계속 반복

마지막에 소수만 남게 된다

def sieve(n):
	is_prime = [True] * (n+1)
	is_prime[0] = False
	is_prime[1] = False

	for candidate in range(2, int(n ** 0.5) + 1):
		if not is_prime[candidate]:
			continue
		for multiple in range(candidate*candidate, n+1, candidate):
			is_prime[multiple] = False

	return [idx for idx, value in enumerate(is_prime) if value]

def prime(n):
    for i in range(2, n // 2 + 1):
        if n % i == 0:
            return False
    return True