파이썬 소수 찾기 알고리즘 (에라토스테네스의 체) 갓벽 가이드

목 차

1. 개요
2. 소수 (Prime Number)
3. 제곱근 (Square Root)
4. 에라토스테네스의 체 (Eratosthenes` sieve) 알고리즘
   • 에라토스테네스의 체의 구체적인 단계
5. 소수 찾는 예제 코드
   • 리스트 요소 값을 바꾸는 방법
   • 리스트 요소를 제거하는 방법
6. 숫자 입력 받아 소수 판별하는 예제 코드

 

개요

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

 

---

 

소수 (Prime Number)

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

 

---

 

제곱근 (Square Root)

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

 

---

 

에라토스테네스의 체 (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의 제곱근까지 반복하면 남은 수들이 모두 소수입니다. (핵심 내용)

 

---

 

소수 찾는 예제 코드

리스트 요소 값을 바꾸는 방법

• 에라토스테네스의 체의 구체적인 단계를 그대로 표현해 보았습니다.
• 숫자 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]
'''

 

리스트 요소를 제거하는 방법

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

💡 프로그래밍 상식 TIP

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

✅ 예제 코드:

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

for j in number_list :
    if j < int(max_number**0.5)+1 :
        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}')
    else :
        break;
    
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]
최종 소수 결과 리스트 : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
'''

 

---

 

숫자 입력 받아 소수 판별하는 예제 코드

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

✅ 예제 코드:

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은(는) 소수입니다.
'''

 

---

 

코즐

파이썬을 배우고 싶은 사람은 누구나 파이썬 학원(국비 지원 파이썬 학원)에 가지 않고도 파이썬 공부를 하면서 실력을 쌓아나갈 수 있다고 생각합니다. 

파이썬 온라인 강의 자료를 올리면서 누구나 쉽게 파이썬을 공부하실 수 있도록 최선을 다해서 설명하도록 하겠습니다.

 

---

 

관련글

• 파이썬 패킹(packing)과 언패킹(unpacking)
• 파이썬 이스케이프 문자 (Escape Characters)
• 파이썬 관계연산자, 논리연산자 문법 정리