[01-3] 에라토스테네스의 체

1. 알고리즘

"C로 배우는 알고리즘"에 설명된 에라토스테네스의 체는 정해진 숫자 이하의 모든 소수를 구하는 것입니다. 이를 위해서 정해진 숫자 크기의 배열을 만들고 진행한다.

2. 실행 코드

최대 9999까지 소수를 모두 출력하도록 합니다. 소수를 구하고, 해당 소수의 배수에 해당하는 숫자들을 지워야 하는데, 해당 숫자에 해당하는 배열의 값을 '1'로 변경해서 소수가 아니라는 것을 표시하였습니다.

MAX_RANGE = 9999

numbers = []
for i in range(MAX_RANGE+1):
    numbers.append(0)

for i in range(2, MAX_RANGE+1):
    # If value is '1', it was deleted
    if numbers[i] == 1:
        continue
    for j in range(i+i, MAX_RANGE+1, i):
        # Delete values which are multiple i. Value '1' means, it was deleted.
        numbers[j] = 1

for i in range(2, MAX_RANGE+1):
    if numbers[i] != 1:
        # To print one line, use 'end=" "'
        print(i, end=" "),
print()

4. Tips

Python2에서는 print문에 ','를 붙여서 서로 다른 라인에서 실행하는 print문을 한줄에 표시할 수 없습니다. 그런데 Python3에서는 이 방법이 동작하지 않습니다. 그래서 'end=" "'를 print문에 추가하여, 한줄에 결과를 출력하도록 하였습니다.

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_01/01_3.py