[수학] 정수론: 소수

모듈러 연산

모듈러 연산은 나눗셈의 나머지 연산을 뜻한다.

쉽게 말하면 어떤 실수 n 을 정수 a로 나누었을 때 발생하는 나머지를 구하는 계산법을 말한다.

파이썬에서는 기호 % 으로 구할 수 있다.

10 % 3 # 1  10 mod 3 : 10을 3으로 나눈 나머지 

소수

소수의 정의

소수는 1보다 크고 자기 자신보다 작은 자연수 두 개를 곱해 만들 수 없는 수를 뜻한다.

즉, 1과 자기 자신 말고는 약수가 없는 자연수를 일컫는다.

합성수는 1보다 큰, 소수가 아닌 자연수를 말한다.

여기서 중요한 건 1은 소수도, 합성수도 아니라는 점이다.

 

소수를 판별하는 방법은 모듈러 연산을 활용한 방법과 에라토스테네스의 체를 활용한 방법, 2가지가 있다.

 

소수 판별법 (1) - 모듈러 연산

p를 a로 나눴을 때 나머지가 0인 a가 있으면 합성수라는 점을 이용한다. (단, 1<a<p)

 

소수 판별법 (2) - 에라토스테네스의 체 적용

에라토스테네스의 체는 주어진 범위에서 소수를 빠르게 찾는 방법으로,

2부터 2의 배수, 3의 배수, 5의 배수, ... 순서로 다음 소수의 배수를 모두 지우고 남는 숫자들이 소수라는 것이다.

즉, 어떤 소수를 찾고 그 소수의 모든 배수를 제거하는 것이 에라토스테네스의 체에서 알고리즘 핵심이다.

 

n보다 작은 모든 소수의 리스트 구하기

def eratosthenes(n):
    sieve = [True] * n  # n개의 True 값이 들어있는 목록 (True는 소수, False는 합성수를 의미)
    
    # 2부터 n까지 하나씩 순차적으로 소수 여부를 판단
    for i in range(2, n):
        # 1. i가 소수인 경우 i의 배수를 False로 변경
        for j in range(i+i, n, i):
            sieve[j] = False
        # 2. i는 소수이므로 True값을 유지
        # return True
        
        
    # 값이 True인 숫자(소수)를 추려낸다.
    result = []
    for i in range(2, n):
        if sieve[i] == True :
            result.append(i)
    return result

 

 

소인수 분해

소인수 분해와 소인수

• 소인수 분해: 소수들의 곱으로 수를 나타낸 것
• 소인수: 소인수 분해의 곱에 사용된 소수

 

 

※ 엘리스《프로그래밍 수학》를 듣고 이해한 바를 정리한 것으로, 사실과 다른 부분이 있을 수 있음.