본 포스팅은 “이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)을 바탕으로 공부한 내용을 정리한 것입니다.
- 소수의 판별
- 에라토스테네스의 체
- 예제
1. 소수의 판별
소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수.
기본적으로 2부터 (x - 1)까지 모든 수를 확인해가며, x가 해당 수로 나누어 떨어진다면 소수가 아니다.
여기에 자연수의 약수가 가지는 특징을 활용한다.
해당 수의 제곱근 (가운데)를 기준으로 약수들이 대칭적인 구조를 가지기 때문에 가운데까지만 확인하면 된다.
1
2
3
4
5
6
7
8
9
import math
# 소수 판별함수
def is_prime_number(x):
# 2부터 x의 제곱근까지 모든 수를 확인하며
for i in range(2, int(mat.sqrt(x)) +1):
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
return False # 소수가 아님
return True # 소수임
해당 알고리즘은 하나의 수를 판별하는데에는 적합하지만, 범위 내의 모든 소수를 찾기에는 비효율적이다.
2. 에라토스테네스의 체
여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표 알고리즘이다.
N 이하의 모든 소수를 찾을 때 사용할 수 있다. 다음과 같은 순서로 진행된다.
- 2부터 N까지의 모든 자연수를 나열한다.
- 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
- 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)
- 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math
# 2부터 1000까지의 모든 수에 대하여 소수 판별
n = 1000
# 처음엔 모든 수가 소수(True)인 것으로 초기화 (0과 1 제외)
array = [True for i in range(n+1)]
# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) +1): # 2부터 n의 제곱근까지 모든 수를 확인하며
if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
# i를 제외한 i의 모든 배수를 지우기
j = 2
while i * j <= n:
array[i * j] = False
j += 1
# 모든 소수 출력
for i in range(2, n+1):
if array[i]:
print(i, end=' ')
메모리가 많이 필요하다는 단점이 있어서 N의 크기가 커지면 비효율적이다.
3. 예제
M 이상 N 이하의 소수를 모두 출력하는 프로그램을 작성하시오.
- 첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 <= M <= N <= 1000000)
- 단, M 이상 N 이하의 소수가 하나 이상 있는 입력만 주어진다.
- 하 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import math
# M과 N을 입력받기
m,n = map(int, input().split())
array = [True for i in range(1000000 +1)] # 모든 수가 소수인것으로 초기화
array[1] = 0 # 1은 소수가 아님
# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) +1): # 2부터 n 제곱근까지 모든 수 확인
if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
# i를 제외한 i의 모든 배수를 제거하기
j = 2
while i * j <= n:
array[i * j] = False
j += 1
# M부터 N까지의 모든 소수 출력
for i in range(m, n+1):
if array[i]:
print(i)
참고
“이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)
- 자료 주소: http://www.hanbit.co.kr/src/10307/
- 저자 깃허브 주소: http://github.com/ndb796
- 동영상 주소: http://youtube.com/user/HanbitMedia93