프로그래머가 보는 수학 - 에라토스테네스의 체

사전지식 : https://aaaag.tistory.com/21

프로그래머가 보는 수학 - 소수와 합성수

---

에라토스테네스의 체 : 임의의 수에서 가장 작은 소수를 찾은 후 그 배수의 수들을 지워서 소수들을 찾는 방법

---

10을 에라토스테네스의 체를 사용해서 소수를 구한다면

• 2~10까지 숫자를 쓴다(1은 소수가 아니니 제외)
• 소수2를 제외한 2의 배수들 2, 4, 6, 8, 10을 제거한다
• 소수3을 제외한 3의 배수들 6, 9를 제거하는데 6은 이미 제거된 상태이다
• 4는 제거되었으니 제외
• 소수5를 제외한 5의 배수들을 제거한다
• 위와 같은 방식으로 10까지 되풀이 한다
• 에라토스테네스의 체 :  2, 3, 5, 7

---

프로그래밍 구현

# -*- coding: utf-8 -*-
import sys

number = int(input())

valueList = []
for value in range(2, number + 1):
    valueList.append(value)

resultList = []
while len(valueList) != 0:
    result = 0
    rValue = valueList[0]
    for lValue in valueList:
        if (lValue % rValue) == 0:
            if result == 0:
                result = rValue

            valueList.remove(lValue)

    resultList.append(result)

print(resultList)