소수 판별: 에라토스테네스의 체 알고리즘

Last Updated

2023/08/20

Tag

Tech

Algorithm

에토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수(prime number)를 찾는 알고리즘

마치 체로 치듯이 수를 걸러낸다고 하여 ‘에라토스테네스의 체’라고 부른다.

Python Code

import math

n = 1000
array = [True for i in range(n+1)]

for i in range(2, int(math.sqrt(n)) + 1):
    if array[i] == True:
        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 = ' ')
Python
복사
Eratosthenes'sieve.py

Disclaimer

본 사이트의 글은 개인적인 의견과 경험을 바탕으로 작성되었으며, 일반적인 참고용으로만 사용해야 합니다. 여기서 제공하는 정보를 바탕으로 한 결정이나 행동은 신중하게 고려해 주세요. 외부 사이트의 내용에 대해서는 책임지지 않으며, 외부 사이트의 정책과 조건에 따릅니다. 모든 콘텐츠는 저작권법에 의해 보호되며, 무단 복제나 도용을 금지합니다. 사용 시 사전 동의를 구해 주세요. 감사합니다.