소수 찾기(feat. 에라토스테네스의 체)

2022. 10. 10. 13:52· 알고리즘

알고리즘 문제에서 소수를 찾으려는데 시간 복잡도에서 걸렸다.
처음 사용한 소수찾는 함수는 다음과 같다.

def get_sosu(num):
    if num == 1:
        return 0

    for i in range(2, num):
        if num % i == 0:
            return 0
    return 1
  • 소수는 1과 자기 자신을 제외한 숫자 외에는 약수가 될 수 없다.
  • 다음과 같은 코드를 통해 2에서부터 자기 자신까지 모두 나눴을 때 나머지가 0이 되면 소수가 아니며, 0이 한번도 나오지 않는다면 소수이다. (완전탐색 방법이다. 시간복잡도는 슬퍼지겠다)
  • 시간복잡도는 O(n) 이 되려나..

아무튼 구하려는 숫자가 커질 수록 시간이 그만큼 늘어나게 되므로 비효율적이다.
소수를 찾는데 가장 효율적인 알고리즘은 에라토스테네스의 체 이다.

 

 

 

파이썬으로 구현한 에라토스테네스의 체는 다음과 같다.

def get_prime_num(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * (n + 1)
 
		# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(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 + 1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
 
    # 소수 목록 산출
    return [i for i in range(2, n + 1) if sieve[i] == True]

- 시간 복잡도는 O(NloglogN)

- 하지만 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다. 

  - 10억이 소수인지 아닌지 판별해야 할 때 에라토스테네스의 체는 사용하기 좋지 않을 수도 있다.

 

 

 

 

참고

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간

ko.wikipedia.org

https://www.youtube.com/watch?v=9rLFFKmKzno 

 

반응형
저작자표시 (새창열림)

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

DFS와 BFS  (0) 2023.03.21
DP (Dynamic Programming, 동적 프로그래밍)  (0) 2022.10.10
방향벡터  (0) 2022.10.03
'알고리즘' 카테고리의 다른 글
  • DFS와 BFS
  • DP (Dynamic Programming, 동적 프로그래밍)
  • 방향벡터
sovelop
sovelop
무슨 생각을 해.. 그냥 하는거지
so's devlog무슨 생각을 해.. 그냥 하는거지
sovelop
so's devlog
sovelop
전체
오늘
어제
  • 분류 전체보기 (141)
    • 🔥TIL (15)
    • 생각 (5)
      • Daily Routine (0)
    • WEB (2)
    • VueJS (1)
    • 파이썬 문법 (17)
      • Django (0)
    • 알고리즘 (23)
      • 백준 알고리즘 (13)
      • 프로그래머스 (0)
      • 기타 사이트 알고리즘 (6)
    • 컴퓨터공학입문 (13)
    • Data_Analysis (9)
    • Javascript (8)
      • 문법 (8)
      • node.js (0)
    • Java (9)
      • 문법 (3)
      • Android Studio (0)
      • Algorithm (2)
    • Server (6)
      • sql (2)
      • linux (2)
    • Back-up (22)
      • Git + Github (5)
      • English (0)
      • etc (17)
    • 테크 관련 세미나 (4)
    • English (0)
    • Error (4)
    • 코테후기 (0)

블로그 메뉴

  • About me

공지사항

인기 글

태그

  • 혼공자
  • 코알라univ
  • 코딩좀알려주라
  • 한빛미디어
  • 혼공단
  • va87m
  • # 백준 #파이썬 #python
  • 무접점저소음

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
sovelop
소수 찾기(feat. 에라토스테네스의 체)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.