소수 판별 알고리즘
소수? 약수가 오로지 1인 수
1을 제외한 수의 배수가 되는 수는 소수가 아니다.
임의의 수 n까지의 소수를 구하고자 할 때, 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제외시키는 방식으로 소수를 찾는다.
에라토스테네스의 체 알고리즘의 시간 복잡도는 사실상 선형 시간에 가까울 정도로 매우 빠르다
각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다
n = int(input())
a = [True] * (n + 1)
m = int(n**0.5)
for i in range(2, m + 1):
if a[i] == True:
for j in range(i + i, n + 1, i):
a[j] = False
print([i for i in range(2, n + 1) if a[i] == True])
def is_prime(n):
if n == 0 or n == 1:
return False
m = int(n**0.5)
for i in range(2, m+1):
if n % i == 0:
return False
return True