[프로그래밍수학] 소수

엘리스에서 제공한 강의와 자료를 보고 정리한 내용입니다.

 

✅ 모듈러연산

모듈러 연산(Modular arithmetic)은 a mod b = c와 같이 표기하며 "a를 b로 나눈 나머지는 c"라는 뜻이다.

즉, 모듈러 연산은 나머지 연산이다.

프로그래밍 언어들은 보통 나머지 연산에 대해 % 기호를 사용한다.

 

 

✅ 소수

소수(Prime number)는 1과 자기 자신을 제외한 어떤 수로도 나누어 떨어지지 않는 1보다 큰 자연수이다.

소수와 반대의 개념으로 1보다 큰 수 중 어떠한 수로 나누어 떨어지는 수를 합성수(Composite number)라고 한다.

1은 소수에도 합성수에도 속하지 않는다.

 

def isPrime(n):
    if n == 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

 

입력으로 들어온 수가 소수인지 판별하는 함수 isPrime의 구현 형태는 위와 같다.

먼저 입력으로 들어온 수가 1인지 판별하여 1이면 소수가 아니므로 바로 False를 리턴한다.

 

입력으로 들어온 수가 1이 아니라면 2부터 n-1까지의 수를 하나씩 나눠보고 나누어 떨어지는지 확인한다.

이때 한 번이라도 나누어 떨어지면 이 수는 합성수이므로 False를 리턴한다.

for문의 순회가 끝났다면 어떠한 수로도 나누어 떨어지지 않았다는 뜻이다.

이러한 경우 이 수는 소수이므로 True를 리턴한다.

 

✔️ 에라토스테네스의 체

에라토스테네스의 체는 소수를 찾는 방법이다.

 

 

에라토스테네스의 체의 알고리즘은 다음과 같다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다

 

이를 파이썬으로 구현하면 다음과 같다.

 

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

 

 

✅ 소인수분해

소인수분해는 어떤 수를 소수들의 곱으로만 나타내는 것을 의미한다.

이때 곱셈에 사용되는 소수들을 소인수라고 한다.

소수의 경우 소수는 자기 자신 외에 나누어 떨어지는 수가 없으므로 이미 소인수분해가 완료된 것으로 간주한다.

 

아직까지 소인수분해를 할 수 있는 충분히 빠른 방법이 밝혀지지 않아 매우 큰 소수에 대해 소인수분해를 하는 계산은  엄청나게 많은 연산을 필요로 한다.

소인수분해의 이러한 특징을 현대 암호에 사용하며 RSA가 암호에 소인수 분해를 사용한 예이다.

 

 

🔍 참조

에라토스테네스의 체 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4