[정수론] 소수 구하기

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃

https://www.youtube.com/watch?v=R1vl8FNAC6Q&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=24

---

소수

1과 자기 자신만을 약수로 가지는 수

 

 

핵심 이론: 에라토스테네스의 체

1. 구하고자 하는 소수의 범위만큼 1차원 리스트 (2부터 시작) 를 생성한다.
2. 첫 번째 수(2)부터 시작하여 선택된 수의 배수를 지운다.
3. 리스트의 끝까지 2번을 반복하면 리스트에 남아 있는 수는 소수가 된다.

 

 

시간 복잡도

이중 for문을 사용하므로 O(n^2)라고 판단할 수 있다. 그러나 2번 과정을 진행하면서 숫자가 계속 지워지기 때문에, 최적화의 정도에 따라 다르겠지만 일반적으로 O(nlog(logn))의 시간 복잡도를 가진다.

배수를 삭제하는 연산으로 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다.

 

 

예시

구하고자 하는 소수의 범위: 30까지

 

1단계: 1차원 리스트 생성

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

 

2단계 - 1: 선택된 숫자 2

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

 

2단계 - 2: 선택된 숫자 3

2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29

 

2단계 - 3: 선택된 숫자 5

2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

 

2단계: 남은 요소에 대하여 모두 반복

 

3단계: 배열에 남은 요소 출력

2, 3, 5, 7, 11, 13, 17, 19, 23, 29