[알고리즘] 소수의 판별 / 약수 / 에라토스테네스의 체 / 파이썬

소수 (Prime Number)

2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다.

단, 1은 소수가 아니다.

 

예)

6은 1,2,3,6 으로 나누어떨어진다.

따라서 6은 소수가 아니다.

 

하지만 7은 1과 7을 제외하고는 나누어떨어지지 않는다.

따라서 7은 소수이다.

 

 

소수 판별법

가장 먼저 어떠한 수 X가 주어졌을 때 해당 수가 소수인지 아닌지 판별하는 방법에 대해서 살펴보자.

가장 간단한 방법은 X를 2부터 X-1까지의 모든 수로 나누어보는 것이다.

만약 2부터 X-1까지의 모든 자연수로 나누었을 때 나누어떨어지는 수가 하나라도 존재한다면 X는 소수가 아니다.

 

코드

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 (x-1)까지의 모든 수를 확인하며
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아니다.
    # 나누어떨어지는 수가 하나도 존재하지 않는다면 소수이다.
    return True


print(is_prime_number(4))
print(is_prime_number(7))

실행 결과

False
True

 

시간복잡도 : O(X)

→ 비효율적

 

---

약수 (Divisor)

어떤 수를 나누어 떨어지게 하는 0이 아닌 정수를 말한다.

1은 모든 수의 약수이고, 자기자신도 약수이다.

어떤 수도 0으로 나눌 수 없기 때문에 0은 어떤 수의 약수도 아니다.

 

예)

16의 약수

1, 2, 4, 8, 16

 

이때 모든 약수에 대하여, 가운데 약수를 기준으로 하여 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 16을 만들 수 있다.

즉, 다음 5개의 등식이 성립하는 것을 알 수 있다.

• 1 x 16 = 16
• 2 x 8 = 16
• 4 x 4 = 16
• 8 x 2 = 16
• 16 x 1 = 16

2 x 8 = 16 은 8 x 2 = 16 과 대칭이다. 즉, 가운데 약수를 기준으로 해서 각 등식이 대칭적인 형태를 보이기 때문에 우리는 특정한 자연수 X가 소수인지 확인하기 위해 바로 가운데 약수까지만 '나누어떨어지는지' 확인하면 된다.

위의 예시에서는 가운데 약수가 4이기때문에 2부터 4까지만 확인하면 된다. 다시 말해 제곱근(가운데 약수)까지만 확인하면 된다.

 

 

16을 2로 나누었을 때 나누어 떨어지기 때문에 16은 소수가 아니다.

 

 

8은 소수인가?

8의 약수는 1, 2, 4, 8 이다.

등식으로 나타내면 다음과 같다.

1 x 8 = 8

2 x 4 = 8

4 x 2 = 8

8 x 1 = 8

우리는 8이 소수인지 확인하기 위해 8의 제곱근까지만 확인하면 된다. 정확히 8의 제곱근은 2.828...이므로 2까지만 나누어떨어지는 확인하면 된다.

8을 2로 나누었을 때 나누어 떨어지기 때문에 8은 소수가 아니다.

 

코드

import math

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아니다.
    return True


print(is_prime_number(4))
print(is_prime_number(7))

실행 결과

False
True

 

시간 복잡도

O(X^2/1)

 

---

에라토스테네스의 체

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 

 

알고리즘

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

예를 들어 N = 16 일 때를 확인해보자.

 

step 0

2부터 16까지의 모든 자연수를 나열한다.

2	3	4	5	6
7	8	9	10	11
12	13	14	15	16

 

step 1

남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거한다.

i = 2 이므로, 2를 제외한 2의 배수는 모두 제외한다.

2	3		5
7		9		11
	13		15

 

step 2

남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거한다.

i = 3 이므로, 3을 제외한 3의 배수는 모두 제외한다.

2	3		5
7				11
	13

 

step 3

남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거한다.

i = 5 이므로, 5을 제외한 5의 배수는 모두 제외한다.

2	3		5
7				11
	13

 

step 4

이어서 마찬가지로, 남은 수 중에서 아직 처리하지 않은 가장 작은 수를 찾은 다음, 그 수를 제외한 배수를 제거하는 과정을 반복한다. 이 과정을 거쳐 남아 있는 수는 모두 소수이며, 이렇게 2부터 26까지의 모든 소수를 찾았다.

 

1부터 16까지의 모든 소수는 2, 3, 5, 7, 11, 13 임을 알 수 있다.

 

 

에라토스테네스의 체 알고리즘은 매 스탭마다 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다고 하였으나, 이때 i는 N의 제곱근(가운데 약수)까지만 증가시켜 확인하면 된다. 

 

코드

import math

# 2부터 n까지의 모든 수에 대하여 소수 판별
n = int(input())
# 처음엔 모든 수가 소수(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=' ')

시간 복잡도

O(NloglogN) 으로 매우 빠르지만, 메모리가 많이 필요하다는 단점이 있다.