[Algorithm] 에라토스테네스의 체

소수가 아닌 수를 모두 걸러내 소수 여부를 판별하는 알고리즘

• 소수 여부를 판별할 숫자만큼의 배열을 생성한다.

number = 100 # 100까지의 숫자에 대한 소수 여부 판별
prime = [True] * (number+1)

• 0과 1은 소수가 아니므로 False 처리한다.

prime[0] = prime[1] = False

• 2부터 시작해 해당 숫자가 소수인지 판별하고
  • 소수라면 해당 숫자의 배수는 모두 소수가 아님(False) 처리한다.
  • 소수가 아니라면 넘어간다(continue).

for i in range(2, number+1):
        if not prime[i]:
                continue
        for j in range(i*2, number+1, i):
                prime[j] = False

이 과정을 거치고 나면 각 숫자에 대해 인덱스로 접근했을 때
소수 여부를 확인할 수 있는 배열이 생성된다.

전체 코드 (Python)

number = int(input()) # 소수 여부를 판별할 자연수 입력
prime = [True] * (number+1)

prime[0] = prime[1] = False
for i in range(2, number+1):
        if not prime[i]:
                continue
        for j in range(i*2, number+1, i):
                prime[j] = False

print("소수입니다." if prime[number] else "소수가 아닙니다.")

# input
100
# output
소수가 아닙니다.

# input
71
# output
소수입니다.