하루살이 개발자

[알고리즘] 소수찾기 - 에라토스테네스의 체 본문

CS/알고리즘

[알고리즘] 소수찾기 - 에라토스테네스의 체

하루살이 2022. 2. 16. 15:44 
def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우 
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

 

임의의 자연수 n이 있으면 그 이하의 소수들을 전부 찾아내는 데 있어서 최적화된 알고리즘!

 

* 관련 문제

https://thrainer.tistory.com/62?category=1007146 

 

[BaekJoon 4948번] 베르트랑 공준(Python)

베르트랑 공준 문제입니다. 문제링크: https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한

thrainer.tistory.com

https://thrainer.tistory.com/63?category=1007146 

 

[BaekJoon 9020번] 골드바흐의 추측 문제(Python)

골드바흐의 추측 문제입니다. 문제링크: https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어,

thrainer.tistory.com

 

'CS > 알고리즘' 카테고리의 다른 글

[알고리즘] 최대공약수(유클리드 호제법) / 최소 공배수  (0) 2022.02.23
[알고리즘] union-find 알고리즘  (0) 2022.02.20
[알고리즘] 우선순위 큐 (Priority Queue)  (0) 2022.02.16
[알고리즘] 최단 경로 알고리즘(1) - 다익스트라(Dijkstra) 알고리즘  (0) 2022.02.13
[알고리즘_그래프] DFS(깊이 우선 탐색) 예제  (0) 2022.01.23
'CS/알고리즘' Related Articles more