[PYTHON/COMMON] 에라토스테네스의 체(Sieve of Eratosthenes)를 사용해 소수 구하기

icodebroker COMMON 2024-06-18

■ 에라토스테네스의 체(Sieve of Eratosthenes)를 사용해 소수를 구하는 방법을 보여준다.

▶ 예제 코드 (PY)


import math

def getPrimeNumberList(value):
    isPrimeNumberList = [True] * value

    maximumLength = math.ceil(math.sqrt(value))

    for i in range(2, maximumLength):
        if isPrimeNumberList[i]:
            for j in range(i + i, value, i):
                isPrimeNumberList[j] = False

    return [i for i in range(2, value) if isPrimeNumberList[i]]

primeNumberList = getPrimeNumberList(100)

print(primeNumberList)

"""
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
"""

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

import math

def getPrimeNumberList(value):

isPrimeNumberList = [True] * value

maximumLength = math.ceil(math.sqrt(value))

for i in range(2, maximumLength):

if isPrimeNumberList[i]:

for j in range(i + i, value, i):

isPrimeNumberList[j] = False

return [i for i in range(2, value) if isPrimeNumberList[i]]

primeNumberList = getPrimeNumberList(100)

print(primeNumberList)

"""

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

"""