온라인 소수 생성기

소수란 무엇인가요?

소수는 1보다 큰 자연수 중에서 1과 자기 자신만으로 나누어떨어지는 수를 말합니다. 가장 작은 소수들은 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… 입니다. 숫자 2는 유일한 짝수 소수입니다. 다른 모든 짝수는 2로 나누어떨어지기 때문입니다.

4 (= 2 × 2), 6 (= 2 × 3), 15 (= 3 × 5)와 같은 숫자들은 소수가 아닙니다. 이러한 숫자들을 합성수라고 부릅니다.

생성기는 어떻게 작동하나요?

범위 내의 모든 소수를 나열하기 위해, 우리는 에라토스테네스의 체를 사용합니다. 이 방법은 기원전 240년경 키레네의 그리스 수학자 에라토스테네스가 고안한 가장 오래되고 효율적인 알고리즘 중 하나입니다.

이 알고리즘은 찾아낸 각 소수의 배수를 순차적으로 지워나갑니다. 남은 것들이 소수가 됩니다. 전체 계산은 귀하의 브라우저에서 직접 이루어지며, 어떠한 데이터도 서버로 전송되지 않습니다.

무작위 선택을 위해, 생성기는 먼저 범위 내의 모든 소수 목록을 구성한 다음, 암호학적으로 안전한 생성기(crypto.getRandomValues())를 사용하여 필요한 개수만큼 무작위로 선택합니다.

생성기의 기능

• 모든 소수 – 지정된 범위 내의 모든 소수를 나열합니다 (최대 10,000개).
• 무작위 선택 – 범위에서 N개의 무작위 소수를 선택합니다 (큰 범위에 적합).
• 정렬 – 결과를 오름차순으로 정렬합니다.
• 구분자 – 복사할 때 숫자를 어떻게 구분할지 선택합니다.
• 빠른 사전 설정 – 가장 자주 사용되는 범위를 한 번의 클릭으로 설정합니다.

소수는 어디에 사용될까요?

암호학과 보안

소수는 현대 암호학의 기본입니다. RSA와 같은 알고리즘은 두 개의 큰 소수를 곱하는 것은 쉽지만, 그 곱을 다시 소인수로 분해하는 것은 계산적으로 매우 어렵다는 원리를 기반으로 합니다.

• RSA 암호화 – 두 개의 큰 소수로부터 키가 생성됩니다.
• 디피-헬만 – 소수 모듈을 사용한 키 교환.
• 해싱 함수 – 소수를 마법 상수(SHA, MD5)로 사용.

수학 및 과학

• 정수론 – 정수의 기본 구성 요소.
• 골드바흐의 추측 – 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있다 (아직 증명되지 않음).
• 리만 가설 – 힐베르트 문제 중 하나로, 소수의 분포와 관련이 있습니다.

실용적인 사용

• 해시 테이블 – 테이블 크기를 소수로 설정하여 충돌 감소.
• 의사 난수 생성기 – 소수 모듈을 사용한 선형 합동.
• 음악 및 리듬 – 소수 길이의 주기를 가진 폴리리듬.

소수의 분포

소수는 자연수 사이에 불규칙하게 분포하지만, 범위가 커질수록 밀도는 감소합니다. 이는 소수 정리로 설명됩니다: N까지의 소수의 개수는 대략 N / ln(N)입니다.

에라토스테네스의 체 단계별 설명

범위 2–30:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

1. 2를 선택하고 그 배수들을 지웁니다: 4, 6, 8, 10, 12...
2. 3을 선택하고 그 배수들을 지웁니다: 9, 15, 21, 27...
3. 5를 선택하고 그 배수들을 지웁니다: 25...
4. √30 ≈ 5.5 → 완료

소수: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

코드에서의 에라토스테네스의 체

JavaScript

function sieve(to) {
  const composite = new Uint8Array(to + 1);
  const primes = [];
  for (let p = 2; p <= to; p++) {
    if (composite[p]) continue;
    primes.push(p);
    for (let j = p * p; j <= to; j += p) composite[j] = 1;
  }
  return primes;
}

Python

def sieve(n):
    composite = bytearray(n + 1)
    primes = []
    for p in range(2, n + 1):
        if not composite[p]:
            primes.append(p)
            for j in range(p * p, n + 1, p):
                composite[j] = 1
    return primes

자주 묻는 질문 (FAQ)