def is_prime_number(x):
# 2부터 (x-1)까지의 모든 수를 확인하며
for i in range(2, x):
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
return False # 소수가 아님
return True # 소수임
print(is_prime_number(4)) # False
print(is_prime_number(7)) # True
import math
# 소수 판별 함수
def is_prime_number(x):
# 2부터 x의 제곱근까지의 모든 수를 확인하며
for i in range(2, int(math.sqrt(x)) + 1):
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
return False # 소수가 아님
return True # 소수임
print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임
하나의 수에 대해서 소수인지 아닌지 판별하는 함수를 작성해보았다.
하지만 소수인지 아닌지 판별해야하는 경우가 아니라, 수의 범위가 주어졌을 때, 그 전체 수의 범위 안에서 존재하는 모든 소수를 찾아야 하는 경우에는 어떻게 해야할까?
에라토스테네스의 체 알고리즘은 다음과 같다.
1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다.
N = 26 이라 가정하고 그림을 그려 이해해보자.
import math
n = int(input()) # 2부터 n까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화
# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
# i를 제외한 i의 모든 배수를 지우기
j = 2
while i * j <= n:
array[i * j] = False
j += 1
# 모든 소수 출력
for i in range(2, n + 1):
if array[i]:
print(i, end=' ')