[Python] 파이썬 숫자 소수 판별 알고리즘 구현

728x90

목 차

• 1. 개요
• 2. 소수 (Prime Number)
• 3. 제곱근 (Square Root)
• 4. 에라토스테네스의 체 (Eratosthenes` sieve) 알고리즘
• 5. 소수 리스트 구하기 : 리스트 요소 값을 바꾸는 방법
• 6. 소수 리스트 구하기 : 역순으로 리스트 요소 삭제 방법
• 7. 숫자를 입력받아 소수 판별

 

 

1. 개요

• 요즘 코딩 테스트에 파이썬으로 숫자를 입력받아 소수인지 판별하는 프로그래밍을 해보라는 문제가 나온다는 얘기를 듣고 '에라토스테네스의 체(Eratosthenes' sieve) 알고리즘'을 파이썬 코딩으로 시도해보았다.
• 해당 소스를 이해하려면 사전 지식으로 소수가 무엇인지, 제곱근이 무엇인지 정도는 미리 알고 있어야 한다.

 

2. 소수 (Prime Number)

• 소수(Prime Number)는 1과 자기 자신을 제외하고는 약수를 가지지 않는 2 이상의 자연수를 말합니다. 즉, 어떤 자연수가 소수라면, 그 수는 1과 자기 자신으로만 나누어 떨어집니다.
• 쉽게 말해서, 나눌 수 있는 수가 자연수 중에 1 밖에 없다는 뜻입니다.

 

 

3. 제곱근 (Square Root)

• 제곱근(Square Root)은 어떤 수를 제곱했을 때 주어진 수가 되는 값입니다. 쉽게 말해서, 어떤 수 xxx의 제곱근은 그 수를 두 번 곱했을 때 나오는 값이 xxx인 수입니다.
• 쉽게 말해서, 3을 제곱하면 9가 되는데 그 반대로 9의 제곱근은 3이라는 얘기입니다.

 

4. 에라토스테네스의 체 (Eratosthenes` sieve) 알고리즘

• 에라토스테네스의 체(Eratosthenes' sieve)는 고대 그리스의 수학자 에라토스테네스가 제안한 알고리즘으로, 주어진 범위 내에서 모든 소수를 빠르고 효율적으로 구하는 방법입니다. 이 알고리즘의 핵심 개념은, 소수는 1과 자기 자신만을 약수로 가지는 수라는 점을 활용하여, 소수의 배수들을 체로 거르는 방식으로 소수가 아닌 수를 제거하는 것입니다.

 

에라토스테네스의 체의 구체적인 단계:

1. 2부터 NNN까지의 수를 나열합니다.
   • 예: N=30N = 30N=30이면, 2, 3, 4, ..., 30까지 나열.
2. 첫 번째 소수인 2를 선택하고, 2의 배수인 4, 6, 8, 10, ..., 30을 모두 지웁니다.
3. 남아있는 수 중에서 가장 작은 수 3을 선택하고, 3의 배수인 6, 9, 12, ..., 30을 지웁니다.
4. 그다음 남아있는 수 중에서 가장 작은 수 5를 선택하고, 5의 배수인 10, 15, 20, ..., 30을 지웁니다.
5. 이 과정을 NNN의 제곱근까지 반복하면 남은 수들이 모두 소수입니다. (핵심 내용)

 

 

5. 소수 리스트 구하기 : 리스트 요소 값을 바꾸는 방법

• 위에 에라토스테네스의 체의 구체적인 단계를 그대로 표현해 보았다.
• 숫자 2부터 입력 받은 숫자 이하의 자연수 범위 중에 소수인 리스트를 구하는 소스입니다.
• 입력 받은 숫자 범위 리스트와 동일한 판별 리스트를 만들고 for문을 통해 판별하면서 판별 리스트의 요소 값을 바꾸는 방식입니다.
• 에라토스테네스의 체 단계 5번을 보시면 제곱근까지만 확인하면 된다고 하여 2부터 제곱근(흔히 루트, 스퀘어)까지만 순회하도록 만들어 주었습니다.
• 불필요한 연산들을 최대한 줄이기 위해 규칙을 찾고 2의 배수, 3의 배수... 순회할 때 범위 끝까지 배수들 모두 판별하도록 만들었습니다.

max_number = int(input("숫자를 입력하시오."))
number_list = list(range(2, max_number+1)) # [2, 3, 4, ... , max_number]
is_prime = [True] * (max_number+1)  # 소수인지 여부를 저장하는 리스트

for j in range(2, int(max_number**0.5)+1):  # 제곱근까지만 확인
    if is_prime[j]:  # j가 소수일 때, 최초 실행 2는 소수
        for k in range(j*j, max_number+1, j):  # j의 배수들을 제거, 불필요한 연산 제거 처리 (연산은 제곱부터 시작)
            if is_prime[k]:
                is_prime[k] = False  # 소수 아님으로 저장

    print(f'순회중인 값 : {j} >> 남은 리스트 {[num for num in number_list if is_prime[num]]}')

result = [num for num in number_list if is_prime[num]]
print(f'최종 소수 결과 리스트 : {result}')

'''
실행 결과
숫자를 입력하시오. 30
순회중인 값 : 2 >> 남은 리스트 [2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
순회중인 값 : 3 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29]
순회중인 값 : 4 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29]
순회중인 값 : 5 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
최종 소수 결과 리스트 : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
'''

 

 

6. 소수 리스트 구하기 : 역순으로 리스트 요소 삭제 방법

• 해당 소스는 에라토스테네스의 체 알고리즘을 보다 직관적으로 보고 만들었습니다.
• 숫자 2부터 입력 받은 숫자 이하의 자연수 범위 중에 소수인 리스트를 구하는 소스입니다.
• 만들어진 숫자 범위 리스트 요소에 직접적으로 접근하여 요소를 삭제하는 방식입니다.

주의사항!

• 리스트를 요소를 삭제할 때는 역순회로 삭제하는게 효율적이다.
• 앞번호부터 지우려고 하면, for문에서 index 범위 에러를 자주 보게 될 것이다. 
• 뒤에서부터 지워주는 방법이 인덱스 범위 에러를 피하는 가장 쉬운 방법이다. (돈주고도 못사는 꿀팁!)

max_number = int(input("숫자를 입력하시오."))
number_list = list(range(2, max_number+1)) # [2, 3, 4, ... , max_number]

for j in number_list :    
    for k in range(len(number_list), 0, -1) : # 리스트를 역순으로 순회
        if j == number_list[k-1] :
            break    
        else :
            if number_list[k-1] % j == 0 :
                number_list.remove(number_list[k-1]) # 리스트에서 직접 제거
                
    print(f'순회중인 값 : {j} >> 남은 리스트 {number_list}')
    
print(f'최종 소수 결과 리스트 : {number_list}')

'''
실행 결과
숫자를 입력하시오. 30
순회중인 값 : 2 >> 남은 리스트 [2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
순회중인 값 : 3 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29]
순회중인 값 : 5 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
순회중인 값 : 7 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
순회중인 값 : 11 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
순회중인 값 : 13 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
순회중인 값 : 17 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
순회중인 값 : 19 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
순회중인 값 : 23 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
순회중인 값 : 29 >> 남은 리스트 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
최종 소수 결과 리스트 : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
'''

 

 

7. 숫자를 입력받아 소수 판별

• 위에 만들어 놓은 소스를 바탕으로 숫자를 입력받아 소수인지 판별하는 소스로 변경해 보았습니다.

max_number = int(input("숫자를 입력하시오."))
is_prime = True

for j in range(2, int(max_number**0.5)+1) : # 제곱근까지만 확인(에라토스테네스 아저씨가 그랬음)
    if max_number % j == 0 :
        is_prime = False
        break

if is_prime :
    print(f'숫자 {max_number}은(는) 소수입니다.')
else :
    print(f'숫자 {max_number}은(는) 소수가 아닙니다.')

'''
실행 결과
숫자를 입력하시오. 10
숫자 10은(는) 소수가 아닙니다.
---------------------------------
숫자를 입력하시오. 25
숫자 25은(는) 소수가 아닙니다.
---------------------------------
숫자를 입력하시오. 79
숫자 79은(는) 소수입니다.
---------------------------------
숫자를 입력하시오. 263
숫자 263은(는) 소수입니다.
'''