파이썬 자료구조/알고리즘 10 : 소수 찾기 알고리즘

파이썬 자료구조/알고리즘 10 : 소수 찾기 알고리즘

 

다음은 for~else문을 이용해서 1~1000까지의 소수를 출력하는 코드입니다.

counter = 0
for n in range(2, 1001):
    for i in range(2, n):
        counter += 1
        if n % i == 0:
            break
    else:
        print(n)
print(f"나눗셈 실행 횟수 : {counter}")

2
3
5
(...)
983
991
997
나눗셈 실행 횟수 : 78022

 

for~else문은 for문이 break 등으로 빠져나가지 않고 끝까지 반복문을 수행했을 때 else문을 실행하는 구조입니다. 또한 for문이 실행되지 않는 경우에도 else문이 실행됩니다.

 

소수는 1과 자기 자신을 제외한 어떤 정수로도 나눠지지 않는 숫자입니다. 따라서 첫 번째 for문에서 1을 범위에서 제외시켰습니다.

 

n이 7인경우 i는 2~6까지의 범위에서 n 나누기 i를 했을 때 나머지가 0이라면 n을 합성 수로 여기고 n을 1 증가시킨 값으로 다시 첫 번째 반복문을 실행합니다. break문은 내부의 for문을 벗어나도록 하기 때문입니다.

 

7은 1과 자기 자기 자신으로밖에 나누어지지 않는 소수이므로 else문을 실행하여 결과적으로 7을 출력하게 될 것 입니다.

 

 

 

 

그러나 이 방법은 불필요한 나눗셈 연산을 많이 하게 됩니다.7의 경우 소수임을 판단하기 위해서 2~6까지의 수로 계속해서 나눠보고 있지만 n의 값이 커지면 나눠봐야 하는 숫자 또한 엄청나게 증가하게 될 것입니다.

 

정수론의 기본 정리에 따르면 모든 자연수는 곱셈의 관점에서 소수를 반드시 포함하고 있습니다.합성수는 1과 자기 자신 외에 다른 수를 약수로 가지는 수이므로

 합성수는 둘 이상의 소수들의 곱이 됩니다.

결국 합성수는 소수로 나누었을 때 나머지가 0이 되는 경우가 반드시 존재하게 됩니다.

 

n의 값이 23244이라고 했을 때, 이것이 소수인지 합성수인지 확인하기 위한 방법으로 2~23243을 차례대로 나누는 방법보다, 지금까지 구한 소수들(2, 3, 5...)로 나누었을 때 0이 되는지 아는지를 확인하는 방법이 훨씬 더 나누기 연산을 줄일 수 있는 방법이 될 수 있습니다.

 

 

다음은 위의 코드를 개선한 코드입니다.

counter = 0    # 나눗셈 횟수
prime = [None] * 500	# 소수 저장
ptr = 0		# 이미 찾은 소수의 개수
prime[ptr] = 2		# 첫번째 소수인 2를 맨 처음값으로 저장
ptr += 1

for n in range(3, 1001, 2):  # 짝수는 모두 합성수이므로 홀수만을 대상으로 함
    for i in range(1, ptr):
        counter += 1
        if n % prime[i] == 0:    # 나누어 떨어지면 합성수이므로 내부 반복문 탈출
            break
    else:				# 어떤 소수로도 나누어지지 않았다면 소수이므로 배열에 등록
        prime[ptr] = n			
        ptr += 1

for i in range(ptr):	# 저장했던 소수들을 출력
    print(prime[i])
print(f"나눗셈 실행 횟수 : {counter}")

(...)
983
991
997
나눗셈 실행 횟수 : 14622

맨 처음 코드에 비해서 나눗셈 실행 횟수가 엄청나게 줄어든 것을 확인할 수 있습니다.

짝수는 모두 합성수이므로 걸러내 버리고 반복문을 통해 prime 배열에 저장한 소수들만을 이용하여 나눗셈을 함으로써 불필요한 연산을 덜어낼 수 있습니다.

 

n이 3인 경우, ptr은 1이므로 안쪽 반복문은 성립되지 않습니다.

for~else문은 for문이 아예 실행되지 않을 경우에도 else문을 실행하므로 prime[1] = 3이 저장될 것입니다.

 

n이 5인 경우, ptr은 2이므로 i값은 1이 됩니다. prime[1] = 3, 소수이므로 n이 소수로 나누어지는 합성수인지에 대한 여부를 판단할 수 있습니다.

이 경우, 내부 반복문을 더 이상 진행할 수 없게 됨으로 else문이 실행됩니다. prime[2] = 5가 새로운 소수로써 저장됩니다.

(2로 나눠지는 경우는 소수에 해당하지 않으므로 prime[0]으로 나누지는 않았습니다.)

 

n이 9인 경우, n은 prime[1]의 값 3으로 나누어지는 합성수입니다. 따라서 break문에 따라 내부 반복문을 탈출하여 외부 반복문에 다시 접근합니다. 합성수이므로 prime배열에 저장하지 않습니다.

 

 

 

어떤 수를 두 수의 곱셈으로 나타난다고 할 때, 

100 =

1 x 100

2 x 50

4 x 25

5 x 20

10 x 10

20 x 5

25 x 4

50 x 2

100 x 1로 나타낼 수 있습니다.

10x10을 기준으로 서로 대칭을 이루고 있습니다. 

위에서 '합성수는 소수로 나누었을 때 나머지가 0이 되는 경우가 반드시 존재하게 됩니다.'라고 했습니다.

 

1 x 100

2 x 50

4 x 25

5 x 20

여기서 5는 소수이며, 100을 소수인 5로 나누었을 때 나머지는 0이므로 100은 합성 수라고 할 수 있습니다.

 

정리하자면, 어떤 수 n을 두 자연수의 곱으로 나타냈을 때, 루트 n값과 작거나 같은 범위에서 반드시 소수가 존재한다는 것을 알 수 있습니다.

n이 100일 때 루트 100은 10이므로, 10보다 작거나 같은 범위에서 5가 100의 소수로 존재합니다.

 

결국 n을 소수로 나누는 범위를 n의 제곱근보다 작거나 같은 범위로 줄인다면 나눗셈 연산을 더 적게 하더라도 소수의 값을 뽑아낼 수 있게 되는 것입니다.

 

counter = 0    # 곱셈 나눗셈 합한 횟수
ptr = 0    # 찾은 소수의 개수
prime = [None] * 500    # 소수 저장하는 배열

prime[ptr] = 2
ptr += 1

prime[ptr] = 3
ptr += 1
    # 2, 3은 소수이므로 배열에 저장
for n in range(5, 1001, 2):
    i = 1
    while prime[i] * prime[i] <= n:
        counter += 2    # 내부 반복문에서 곱셈과 나눗셈을 연달아 진행하므로 2씩 증가
        if n % prime[i] == 0:
            break
        i += 1
    else:    # 소수이므로 배열에 저장
        prime[ptr] = n
        ptr += 1
        counter += 1    # 나눗셈만 연산한 결과이므로 1씩 증가

for i in range(ptr):    # 소수 출력
    print(prime[i])
print(f'곱셈, 나눗셈 실행 횟수 : {counter}')

983
991
997
곱셈, 나눗셈 실행 횟수 : 3774

 

홀수의 경우와 나누는 소수의 값이 n의 제곱근보다 같거나 작을 때를 범위로 잡고, n의 값에다가 나눴을 때 0으로 나누어 떨어지지 않는 경우를 prime배열에 저장합니다.

 

 

---

(22-02-27 추가)

n의 제곱근을 int(n**0.5)로 표현할 수 있다는 것을 알게 되었음.

 

에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. (반복)

def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True
 
 
M, N = map(int, input().split())
 
for i in range(M, N + 1):
    if isPrime(i):
        print(i)

입력 >>1 15
출력 >>
2
3
5
7
11
13

 

입력 받은 두 값의 범위 내에서 소수를 판별한다.

(1이상 15이하)

해당 범위에서 1과 해당 수를 제외한 나머지 숫자로 나누어 떨어지면 소수가 아님을 판별한다.

 

2는 소수중에 유일한 짝수다.

2의 제곱근은 1.414...이므로 

else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

여기 반복문이 성립하지 않기 때문에 True를 반환한다.