프로그래밍에서의 소수와 모듈러 연산: 알고리즘의 시작

컴퓨터 과학을 공부하다 보면 정수론의 개념들이 슬금슬금 튀어나온다.
특히 소수(Prime Number), 모듈러(Modular) 연산, 소인수 분해 같은 개념은
암호학부터 알고리즘 문제 풀이까지 폭넓게 쓰인다.

이번 글에서는 이 개념들을 하나씩 정리해보고, 실제로 Python 코드로 구현하는 예제도 살펴본다.

📌 1. 모듈러 연산이란?

모듈러 연산(Modular Arithmetic)은 나머지 연산이라고도 부른다.
쉽게 말해, 어떤 수를 다른 수로 나눈 뒤 남는 나머지를 구하는 연산이다.

예:

print(10 % 3)  # 출력: 1

즉, 10을 3으로 나누면 몫은 3이고 나머지는 1 → 그게 10 % 3 = 1

🤔 왜 중요할까?

컴퓨터 내부의 이진수(0과 1) 표현에서 모듈러 연산은 매우 유용하다.

시간 계산 (시계: 24시간 → % 24)
배열의 순환 처리
암호화 알고리즘 (예: RSA)

📌 2. 프로그래밍에서의 소수(Prime Number)

소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 정수다.
예: 2, 3, 5, 7, 11, 13, ...

소수는 정수론에서 굉장히 중요한 역할을 하고,
프로그래밍에서도 종종 등장하는 주제다.

소수를 판별하는 가장 기본적인 코드

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5)+1):  # √n까지만 확인
        if n % i == 0:
            return False
    return True

print(is_prime(13))  # True

📌 3. 소수를 빠르게 찾는 방법: 에라토스테네스의 체

하나하나 나눠보면서 소수를 판별하는 건 효율이 떨어진다.
그래서 나온 고전적인 알고리즘이 바로 에라토스테네스의 체 (Sieve of Eratosthenes)

🔍 아이디어

2부터 n까지 리스트를 만든다.
가장 작은 소수부터 시작해서 그 배수들을 모두 지운다.
남은 수들은 모두 소수다.

코드 예시

def sieve(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False

    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False

    return [i for i in range(2, n+1) if primes[i]]

print(sieve(30))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

📌 4. 소인수 분해 (Prime Factorization)

소인수 분해란 어떤 정수를 소수의 곱으로 나타내는 것을 말한다.
예: 60 → 2 × 2 × 3 × 5

이 개념은 영어로 Prime Factorization이라고 한다.
암호학, 수학 퍼즐, 계산 최적화 등 다양한 곳에 쓰인다.

코드 예시

def prime_factors(n):
    result = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            result.append(i)
            n = n // i
        else:
            i += 1
    if n > 1:
        result.append(n)
    return result

print(prime_factors(60))  # [2, 2, 3, 5]

🎯 마무리

정수론의 개념들은 프로그래밍 알고리즘에서 단순한 수학을 넘어서
효율성, 암호 보안, 최적화와 연결된다.

모듈러 연산은 다양한 실생활 문제 해결에 필수
소수 판별은 암호학 기초
에라토스테네스의 체는 빠른 소수 탐색
소인수 분해는 수의 구조를 이해하는 핵심 도구