Skip to content

zerohertzLib.algorithm.prime

Functions:

Name Description
soe

Sieve of Eratosthenes

soe 

soe(n_max: int) -> list[int]

Sieve of Eratosthenes

Parameters:

Name Type Description Default
n_max int

구하고자 하는 소수 범위의 최댓값

 required

Returns:

Type Description
list[int]

N까지 존재하는 소수 list

Examples:

>>> zz.algorithm.soe(10)
[2, 3, 5, 7]
Source code in zerohertzLib/algorithm/prime.py 
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def soe(n_max: int) -> list[int]:
    """Sieve of Eratosthenes

    Args:
        n_max: 구하고자 하는 소수 범위의 최댓값

    Returns:
        N까지 존재하는 소수 list

    Examples:
        >>> zz.algorithm.soe(10)
        [2, 3, 5, 7]
    """
    visited = [False, False] + [True] * (n_max - 1)
    prime_numbers = []
    for i in range(2, n_max + 1):
        if visited[i]:
            prime_numbers.append(i)
            for idx in range(2 * i, n_max + 1, i):
                visited[idx] = False
    return prime_numbers