소수 계산기
정수가 소수인지 합성수인지 판별하고, 소인수분해 과정과 연관 수학 도구를 확인하세요.
✓ 97은(는) 증명된 소수입니다: √97까지 약수가 존재하지 않습니다 — 정확히 두 개의 서로 다른 양의 약수: 1과 자기 자신
계산 과정 및 나눗셈 단계 보기
n이 소수인지 확인하기 위해 n까지의 모든 수로 나눌 필요는 없습니다. 그 수의 제곱근 이하인 소수들만 나누어 보면 충분합니다: d ≤ ⌊√n⌋.
소수 계산기 작동 방식
최고의 반응 속도, 수학적 엄밀성, 교육적 명확성을 위해 설계되었습니다.
인터랙티브 계산 흐름도
계산 과정을 단계별로 확인하려면 클릭하세요:정수 입력
입력란에 자연수를 입력하거나 준비된 예시 칩을 클릭하세요.
판별 버튼 클릭
제곱근까지의 시험 나눗셈 또는 64비트 결정론적 밀러-라빈 검사를 수행합니다.
결과 확인
수학적으로 증명된 결과, 나눗셈 과정, 소인수, 인접 소수를 확인하세요.
소수 도구 모음
특정 수학적 연산과 탐구를 위해 개발된 전문 계산기들입니다.
소수 생성기
원하는 범위의 모든 소수 목록을 생성하고 CSV로 즉시 복사하세요.
도구 열기 →소인수분해 계산기
합성수를 소수의 거듭제곱으로 분해하고 인터랙티브 인수 나무를 확인하세요.
도구 열기 →다음 및 이전 소수
입력값의 바로 앞뒤에 위치한 가장 가까운 소수를 정확한 거리와 함께 확인하세요.
도구 열기 →N번째 소수
순서 번호로 소수를 검색하세요: 1번째(2)부터 10,000번째(104,729)까지.
도구 열기 →소수의 합
BigInt 정밀도를 사용하여 특정 구간 내 모든 소수의 합을 정확하게 구합니다.
도구 열기 →두 수 사이의 소수
두 경계 사이의 소수를 세고, 밀도와 쌍둥이 소수 쌍을 분석하세요.
도구 열기 →서로소 판별기
유클리드 호제법과 기하학적 격자 채우기를 통해 gcd(a, b) = 1인지 판별합니다.
도구 열기 →소수 계량 함수 π(x)
1억 이하의 소수 밀도 감소를 가우스의 소수 정리와 비교해 보세요.
도구 열기 →1–100 소수표
에라토스테네스의 체 시뮬레이터가 포함된 10×10 인터랙티브 격자판.
도구 열기 →Factor Tree Calculator
Interactive visual factor tree. Watch numbers branch step by step into their prime factors.
도구 열기 →Twin Prime Calculator
Find twin prime pairs (primes that differ by just 2, like 11 and 13) and see how often they appear.
도구 열기 →Prime Gap Calculator
Find the distances between back-to-back prime numbers and spot large gaps.
도구 열기 →Sieve of Eratosthenes
Interactive animated visualizer crossing off multiples step by step to reveal prime numbers.
도구 열기 →Bulk Prime Checker
Check up to 500 numbers at the same time to see which are prime and export to CSV.
도구 열기 →Random Prime Generator
Generate truly random prime numbers with custom digit lengths.
도구 열기 →Prime Number Theorem
Compare the exact count of prime numbers against famous mathematical estimation formulas.
도구 열기 →Goldbach Calculator
Find pairs of prime numbers that add up to any even number you choose.
도구 열기 →Semiprime Calculator
Analyze numbers made by multiplying exactly two prime numbers together (like 15 = 3 × 5).
도구 열기 →Mersenne Prime Calculator
Test huge primes written as 2^p - 1 and explore world-record prime numbers.
도구 열기 →Prime Power Calculator
Test if a number is a prime raised to a power (like 2³ = 8 or 3² = 9).
도구 열기 →Special Prime Checker
Explore fascinating prime families like palindrome primes, twin primes, and mirror primes.
도구 열기 →Prime Distribution & Ulam Spiral
View prime numbers plotted on a visual 2D spiral to discover line patterns.
도구 열기 →RSA Prime Demo
Interactive visual demonstration of how prime numbers lock and protect secret messages online.
도구 열기 →Fraction Prime Factorization
Break down fractions into prime factors and simplify them easily.
도구 열기 →How to Check If a Number Is Prime
Simple algorithms and copyable code examples in Python, JavaScript, C++, Java, and Go.
도구 열기 →소수(Prime Number)란 무엇인가?
정수론과 산술의 분해할 수 없는 가장 기본적인 구성 요소.
기하학적 모델: 직사각형 소수 판별 테스트
n개의 타일로 1 × n 모양의 한 줄만 만들 수 있다면 n은 소수입니다. 너비 > 1인 직사각형을 만들 수 있다면 합성수입니다.
정의와 예시
수학에서 소수는 1보다 큰 자연수 중에서 양의 약수가 1과 자기 자신뿐인 수를 의미합니다.
처음 10개의 소수는 다음과 같습니다: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
1보다 큰 자연수 중 소수가 아닌 수를 합성수라고 부르며, 작은 소수들의 곱으로 나타낼 수 있습니다.
0과 1이 소수가 아닌 이유
0은 소수도 합성수도 아닙니다: 0을 0이 아닌 수로 나누면 나머지가 항상 0이므로 약수가 무한히 많습니다.
1은 소수도 합성수도 아닙니다: 약수가 자기 자신 하나뿐입니다. 1을 소수로 인정하면 산술의 기본 정리인 소인수분해의 유일성이 깨지게 됩니다.
Classification map of whole numbers: 0 (zero divisors rule), 1 (unit), Primes (2 factors), and Composites (3+ factors).
소수와 합성수 비교
자연수의 두 부류 간 핵심적인 수학적 차이점:
| 속성 | 소수 | 합성수 |
|---|---|---|
| 정의 | 정확히 두 개의 서로 다른 양의 약수: 1과 자기 자신 | 3개 이상의 양의 약수 |
| 약수의 개수 | 정확히 2개 | 3개 이상 |
| 가장 작은 수 | 2 (유일한 짝수 소수) | 4 (2 × 2) |
| 소인수분해 | 자기 자신 (p¹) | 소수 거듭제곱의 유일한 곱 (p₁ᵃ × p₂ᵇ …) |
| 짝수 정수 | 오직 2만 소수이며, 다른 모든 짝수는 합성수 | 2보다 큰 모든 짝수 정수 (4, 6, 8, 10, 12…) |
| 예시 | 2, 3, 5, 7, 11, 13, 97, 101 | 4, 6, 8, 9, 12, 51, 91, 100 |
왜 2만 유일한 짝수 소수일까?
짝수는 2로 나누어떨어지는 수입니다. 숫자 2는 약수가 1과 2뿐이어서 정의를 만족합니다. 반면 2보다 큰 모든 짝수는 1, 2, 자기 자신을 약수로 가져 최소 3개 이상의 약수를 갖습니다.
7과 9는 소수인가요?
7은 소수입니다: 약수가 1과 7뿐입니다. 9는 소수가 아닙니다: 3으로 나누어떨어집니다 (3 × 3 = 9). 홀수라고 해서 모두 소수인 것은 아닙니다!
어떤 수가 소수인지 확인하는 방법
고전적인 제곱근 약수 한계와 단계별 검사 알고리즘.
시뮬레이터: 제곱근 한계와 시험 나눗셈
⌊√n⌋ 한계가 소수 판별에 필요한 나눗셈 횟수를 얼마나 획기적으로 줄여주는지 확인하세요.
√n까지의 나누어떨어짐 검사
√n 까지만 나누어보기
n이 소수인지 확인하기 위해 n까지의 모든 수로 나눌 필요는 없습니다. 그 수의 제곱근 이하인 소수들만 나누어 보면 충분합니다: d ≤ ⌊√n⌋.
성립 원리: 약수는 항상 짝을 지어 나타납니다 (a × b = n). 만약 두 약수가 모두 √n보다 크다면 곱이 n을 초과하게 되어 모순이 발생합니다.
예시: 97은 소수일까?
- √97 ≈ 9.848을 계산합니다. 9 이하의 소수만 테스트합니다.
- 테스트할 소수는 2, 3, 5, 7입니다.
- 97 ÷ 2 = 48 나머지 1 (나누어떨어지지 않음, 홀수 7로 끝남).
- 97 ÷ 3 = 32 나머지 1 (나누어떨어지지 않음, 각 자릿수의 합 9+7=16은 3으로 나누어떨어지지 않음).
- 97 ÷ 5 = 19 나머지 2 (나누어떨어지지 않음, 0이나 5로 끝나지 않음).
- 97 ÷ 7 = 13 나머지 6 (나누어떨어지지 않음).
- ≤ √97인 모든 소수 후보가 97을 나누어떨어지게 하지 못했습니다. 따라서 97은 소수임이 증명되었습니다!
예시: 91은 왜 합성수일까?
- √91 ≈ 9.539를 계산합니다. 9 이하의 소수만 테스트합니다.
- 테스트할 소수는 2, 3, 5, 7입니다.
- 91 ÷ 2 = 45 나머지 1 (나누어떨어지지 않음).
- 91 ÷ 3 = 30 나머지 1 (나누어떨어지지 않음, 자릿수 합 9+1=10).
- 91 ÷ 5 = 18 나머지 1 (나누어떨어지지 않음, 0이나 5로 끝나지 않음).
- 91 ÷ 7 = 13 나머지 0 (나누어떨어짐!).
- 7이 약수이므로 91은 합성수입니다: 91 = 7 × 13.
암산 배수 판별 단축법
간단한 암산 규칙을 사용하면 많은 합성수 후보를 빠르게 제외할 수 있습니다:
- 2로 나누어떨어짐: 마지막 자릿수가 짝수 (0, 2, 4, 6, 8).
- 3으로 나누어떨어짐: 모든 자릿수의 합이 3의 배수 (예: 51의 경우 5+1=6이므로 51 ÷ 3 = 17).
- 5로 나누어떨어짐: 마지막 자릿수가 0 또는 5.
- 6k ± 1 규칙: 3보다 큰 모든 소수는 6k − 1 또는 6k + 1 형태로 쓸 수 있습니다. 이 형태의 모든 수가 소수는 아니지만, 이 형태가 아닌 수는 무조건 합성수입니다!
배수 판정법과 소수 판별 지름길
계산기 없이도 합성수를 빠르게 걸러내기 위한 유용한 암산 규칙들.
인터랙티브 도표: 모듈로 6 휠 (6k ± 1)
3보다 큰 모든 소수는 예외 없이 6k + 1 또는 6k - 1 형태를 갖습니다.
| 제수 | 배수 판정법과 착안점 | 적용 예시 | Live Result |
|---|---|---|---|
| 2 | 마지막 자릿수가 짝수: 0, 2, 4, 6, 또는 8. | 248은 8로 끝남 → 2로 나누어떨어짐 | |
| 3 | 모든 개별 자릿수의 합이 3으로 나누어떨어짐. | 453 → 4+5+3 = 12 (3으로 나누어떨어짐) → 3으로 나누어떨어짐 | |
| 4 | 마지막 두 자리로 이루어진 수가 4로 나누어떨어짐. | 3,116은 16으로 끝남 (16 ÷ 4 = 4) → 4로 나누어떨어짐 | |
| 5 | 마지막 자릿수가 0 또는 5. | 895는 5로 끝남 → 5로 나누어떨어짐 | |
| 6 | 2의 배수 테스트(짝수)와 3의 배수 테스트(자릿수 합)를 모두 통과함. | 732는 짝수이고 7+3+2 = 12 → 6으로 나누어떨어짐 | |
| 7 | 마지막 자릿수를 두 배하여 나머지 앞부분에서 뺀 결과가 7로 나누어떨어짐. | 672 → 67 − (2×2) = 63 (63 ÷ 7 = 9) → 7로 나누어떨어짐 | |
| 8 | 마지막 세 자리로 이루어진 수가 8로 나누어떨어짐. | 5,128은 128로 끝남 (128 ÷ 8 = 16) → 8로 나누어떨어짐 | |
| 9 | 모든 개별 자릿수의 합이 9로 나누어떨어짐. | 2,871 → 2+8+7+1 = 18 (18 ÷ 9 = 2) → 9로 나누어떨어짐 | |
| 11 | 자릿수의 교대합(더하기-빼기-더하기...)이 0이거나 11의 배수. | 913 → 9 − 1 + 3 = 11 → 11로 나누어떨어짐 | |
| 13 | 마지막 자릿수의 4배를 나머지 앞부분에 더한 합이 13으로 나누어떨어짐. | 299 → 29 + (9×4) = 65 (65 ÷ 13 = 5) → 13으로 나누어떨어짐 |
6k ± 1 소수 규칙
3보다 큰 모든 소수는 예외 없이 6k + 1 또는 6k - 1 형태를 갖습니다.
이것이 보장되는 이유: 모든 정수는 여섯 가지 형태 중 하나로 나눌 수 있습니다: 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5 (이는 6(k+1)−1과 같음).
- 6k, 6k+2, 6k+4는 항상 짝수(2로 나누어떨어짐)입니다.
- 6k+3은 항상 3으로 나누어떨어집니다.
중요 경고: 이는 필요조건이지 충분조건이 아닙니다. 3보다 큰 모든 소수는 이 형태를 가지지만, 이 형태의 일부 숫자는 합성수입니다 (예: 25 = 6(4)+1 및 35 = 6(6)−1). 항상 제한된 시험 나눗셈을 사용하여 후보를 검증하세요.
왜 소수를 만드는 단순한 공식은 없을까?
1772년 레온하르트 오일러는 모든 정수 n = 0, 1, 2, ..., 39에 대해 오직 소수만을 생성하는 놀라운 이차 다항식 f(n) = n² + n + 41을 발견했습니다 (40개의 연속된 소수: 41, 43, 47, 53, 61, ..., 1601).
그러나 n = 40에서 이 다항식은 40² + 40 + 41 = 1,681 = 41²을 생성하며, 이는 상수가 아닌 어떤 대수 다항식도 무한히 소수만 독점적으로 생성할 수 없음을 증명합니다.
1부터 100까지 소수표
10×10 시각적 격자판. 에라토스테네스의 체 시뮬레이터로 합성수가 지워지는 과정을 관찰하세요.
1부터 1,000까지의 소수
1과 1,000 사이에는 정확히 168개의 소수가 존재합니다.
분포 차트: 백단위 구간별 소수 분포
각 백단위 막대를 클릭하여 해당 구간의 소수를 필터링하세요.
1,000 이하 168개 소수 전체 보기
아래 소수를 클릭하면 계산기에 로드됩니다.
소수 수열의 주요 이정표
정수론과 컴퓨터 과학에서 중요한 기준이 되는 대표적인 소수들입니다.
주요 소수 수열 이정표
이 벤치마크 소수들은 수학, 컴퓨팅 테스트 및 정수론에서 중요한 경계를 나타냅니다:
#1 → 2
p₁ = 2가장 작은 소수이자 첫 번째 양의 소수이며, 존재하는 유일한 짝수 소수입니다. 이후의 모든 소수는 홀수 정수입니다.
#25 → 97
p₂₅ = 97가장 큰 두 자리 소수입니다. 1과 100 사이에는 정확히 25개의 소수가 있으며, 십진법 두 자리 정수의 25%를 차지합니다.
#100 → 541
p₁₀₀ = 541이정표가 되는 100번째 소수입니다. 처음 100개의 소수가 완성되는 지점으로, 이 범위에서 전체 소수 밀도는 18.5%입니다.
#1,000 → 7,919
p₁₀₀₀ = 7,9191000번째 소수입니다. 숫자가 커질수록 소수가 점차 희소해진다는 것을 증명합니다: 1,000개의 소수를 찾는 데 7,919개의 정수가 필요합니다 (밀도 12.6%).
#5,000 → 48,611
p₅₀₀₀ = 48,6115000번째 소수입니다. 50,000 임계값 바로 아래에 위치하며 약 10.3%의 국소 밀도를 보입니다.
#10,000 → 104,729
p₁₀₀₀₀ = 104,72910,000번째 소수 벤치마크입니다. 당사의 즉각적인 테이블 조회는 서버 지연 없이 이 경계까지의 모든 소수를 다룹니다.
소수 계량 함수 π(x)와 밀도
수가 커질수록 소수가 드물어지는 자연 법칙과 가우스의 소수 정리.
10의 거듭제곱별 소수 개수
숫자가 커질수록 소수는 희소해지지만 여전히 무한히 존재합니다. x가 커짐에 따라 소수 정리 근사치 x / ln(x)가 상대적 백분율에서 어떻게 더 가까워지는지 확인하세요:
| 상한값 (x) | 정확한 π(x) | 소수 밀도 (%) | 가우스 근사치: x / ln(x) | 상대 오차 (%) |
|---|---|---|---|---|
| 10 | 4 | 40.00% | 4.34 | +8.5% |
| 100 | 25 | 25.00% | 21.71 | −13.1% |
| 1,000 | 168 | 16.80% | 144.76 | −13.8% |
| 10,000 | 1,229 | 12.29% | 1,085.74 | −11.7% |
| 100,000 | 9,592 | 9.59% | 8,685.89 | −9.4% |
| 1,000,000 | 78,498 | 7.85% | 72,382.41 | −7.8% |
| 10,000,000 | 664,579 | 6.65% | 620,420.69 | −6.6% |
| 100,000,000 | 5,761,455 | 5.76% | 5,428,681.02 | −5.8% |
소수 계량 함수 π(x)란?
정수론에서 π(x)는 기하학적 상수 π ≈ 3.14159를 의미하지 않습니다. 대신 카를 프리드리히 가우스가 이끄는 18세기 수학자들은 x보다 작거나 같은 소수의 정확한 개수를 나타내는 소수 계량 함수(Prime Counting Function)를 표기하기 위해 그리스 문자 π('다수'를 의미하는 plēthos에서 유래)를 채택했습니다.
대수 함수와 달리 π(x)는 x가 소수를 지날 때마다 1씩 증가하는 계단 함수입니다.
소수 정리(PNT) 해설
1896년 자크 아다마르와 샤를 장 드 라 발레 푸생이 독자적으로 증명한 소수 정리는 x가 무한대에 가까워질 때 소수의 분포가 다음을 따른다는 것을 보여줍니다:
이 정리는 x 근처에서 무작위로 선택된 정수가 소수일 확률이 약 1 / ln(x)임을 보여줍니다.
범위 내 소수 찾기
임의의 두 수 사이에 있는 소수를 모두 찾고 개수와 BigInt 합계를 구합니다.
다음 및 이전 소수 구하기
가장 인접한 앞뒤 소수를 확인하고, 정확한 거리를 계산하며, n 이하의 최대 소수를 찾습니다.
엄격한 이웃 vs 포함 경계
인접한 소수를 찾을 때 수학적 정밀성을 위해 엄밀히 인접한 소수와 경계를 포함하는 범위를 구분해야 합니다:
- 엄밀한 이전 소수 (p < n): n보다 엄밀히 작은 가장 큰 소수입니다. n = 97인 경우 이전 소수는 89입니다.
- 엄밀한 다음 소수 (p > n): n보다 엄밀히 큰 가장 작은 소수입니다. n = 97인 경우 다음 소수는 101입니다.
- n 이하의 가장 큰 소수 (≤ n): n 자체가 소수(예: 97)이면 ≤ 97인 가장 큰 소수는 97입니다. n이 합성수(예: 90)이면 89입니다.
베르트랑 공준과 등거리 소수
다음 소수는 얼마나 멀리 있을 수 있을까요? 1850년 파프누티 체비쇼프는 베르트랑 공준을 증명했습니다. 임의의 정수 n > 3에 대해 항상 다음을 만족하는 소수 p가 적어도 하나 존재합니다:
동일 거리 동점: 일부 숫자의 경우 이전 소수와 다음 소수가 정확히 같은 거리에 있습니다. 예를 들어 n = 6의 경우 이전은 5(거리 1)이고 다음은 7(거리 1)입니다. 둘 다 가장 가까운 소수입니다!
단계별 소인수분해 계산
모든 합성수가 소수들의 거듭제곱 곱으로 고유하게 분해되는 과정.
대화형 인수 트리 및 나눗셈 사다리 다이어그램
임의의 정수를 입력하여 시각적 SVG 인수 트리와 단계별 나눗셈 사다리를 모두 생성하세요.
서로소(Coprime) 판별기
유클리드 호제법을 사용하여 두 수가 1 외에 공약수를 갖지 않는지 판별합니다.
유클리드는 gcd(a, b)를 찾는 것이 빈틈이나 겹침 없이 a × b 직사각형을 완벽하게 채울 수 있는 가장 큰 정사각형 타일을 찾는 것과 동일하다는 것을 발견했습니다:
유클리드 호제법 나눗셈 단계
두 합성수가 서로소(Coprime)가 될 수 있나요?
네, 물론입니다! 이것은 초등 정수론에서 가장 널리 오해되는 개념 중 하나입니다. 두 수는 그 자체로 소수인지 여부와 관계없이 최대공약수가 1이면 서로소(상대적 소수)입니다.
8 = 2³(합성수)과 9 = 3²(합성수)을 생각해 보세요. 두 숫자 모두 소수가 아닙니다! 하지만 두 수의 소인수분해가 공통된 소수를 공유하지 않기 때문에 gcd(8, 9) = 1이 되어 완전한 서로소가 됩니다.
암호학에서 서로소가 중요한 이유
- 오일러 피 함수 φ(n): n까지의 정수 중 n과 서로소인 수의 개수를 셉니다. 소수 p의 경우 φ(p) = p − 1입니다.
- RSA 키 생성: 모듈러 곱셈 역원 d가 존재하려면 공개 지수 e가 φ(n) = (p − 1)(q − 1)과 엄밀히 서로소여야 합니다.
- 해시 분포: 서로소인 해시 버킷 크기를 선택하면 고성능 컴퓨터 해시 테이블에서 해시 클러스터링을 방지할 수 있습니다.
소수처럼 보이는 수 (하지만 합성수)
학생들과 프로그래머들이 자주 소수로 오인하는 함정 합성수 모음.
91 해부: 가장 유명한 가짜 소수
인지적 사각지대 (Cognitive Blindspot)
91은 1로 끝나므로 짝수 검사(2)를 통과합니다. 자릿수 합이 9+1=10이므로 3을 통과합니다. 5로 끝나지도 않습니다. 7과 13의 곱은 일반적인 초등 구구단에 없기 때문에 사람들은 무의식적으로 91이 소수일 것이라고 가정합니다!
특별한 유형의 소수들
흥미로운 대수적 특성을 지닌 독특한 소수 군집을 탐구해 보세요.
Quick Special-Prime Scanner
Test any prime to see every special mathematical family it belongs to simultaneously.
특별한 소수 그룹
흥미로운 대수적 특성을 지닌 독특한 소수 군집을 탐구해 보세요.
쌍둥이 소수 (Twin Primes)
차이가 정확히 2인 소수 쌍 (p, p + 2)입니다. 유명한 미해결 난제인 쌍둥이 소수 추측은 이러한 쌍이 무한히 많다고 가정합니다.
메르센 소수 (Mersenne)
2ᵖ − 1 형태로 쓸 수 있는 소수로, 지수 p 자체가 소수여야 합니다. 짝수 완전수와 직접 연결되어 있으며 알려진 가장 큰 소수들을 형성합니다.
소피 제르맹 소수
소수 p에 대해 2p + 1도 소수(안전 소수라고 함)이면 p는 소피 제르맹 소수입니다. 이들은 암호화 프로토콜에서 필수적인 역할을 합니다.
대칭수 소수 (Palindromic)
십진법에서 앞에서 읽으나 뒤에서 읽으나 똑같은 소수입니다. 놀랍게도 11을 제외한 모든 회문 소수는 자릿수가 홀수입니다!
우리 알고리즘의 작동 방식
수학적 엄밀함과 정밀한 증명 단계를 명시하는 투명한 계산 체계.
흐름도: 엔진 의사결정 파이프라인
임의의 정수를 판별하기 위해 엔진이 실행하는 명확한 검사 경로.
작은 정수: 시험 나눗셈
1,000,000,000,000 (10¹²)까지의 입력에 대해서는 ⌊√n⌋까지 6k ± 1 수열을 사용하는 제한된 시험 나눗셈을 실행합니다. 약수가 발견되지 않으면 소수임이 수학적으로 증명됩니다.
범위 목록: 에라토스테네스의 체
범위 쿼리의 경우 엔진은 O(n log log n) 복잡도를 가진 최적화된 비트셋 에라토스테네스의 체를 활용하여 합성수 배수를 정확하게 필터링합니다.
큰 정수: 결정론적 밀러-라빈
2⁶⁴ − 1 (1,844경)까지의 숫자에 대해서는 밑 (2, 325, 9375, 28178, 450775, 9780504, 1795265022)을 사용하는 결정론적 7-밑 밀러-라빈 소수 판별법을 사용합니다. 이는 확률적 오차 없이 무조건적인 결정론적 확실성을 제공합니다.
정밀한 BigInt 연산
모든 대규모 계산은 2⁵³ − 1 (9,007,199,254,740,991)을 초과하는 IEEE-754 64비트 부동소수점 반올림 오차를 방지하기 위해 JavaScript 네이티브 BigInt 객체를 통해 처리됩니다.
| 기능 / 모드 | 수학적 기법 | 보장 범위 | 증명 확실성 |
|---|---|---|---|
| 소수 판별 | Square root check & advanced prime test | Numbers up to 18 quintillion | 결정론적 증명 (오차 0%) |
| 소인수분해 | Step-by-step division test | Numbers up to 1 trillion | 결정론적 증명 (오차 0%) |
| N번째 소수 | Fast prime sequence lookup | Up to the 10,000th prime (104,729) | 결정론적 증명 (오차 0%) |
| 범위 내 소수 | Prime grid sieve | Ranges up to 10,000 numbers | 결정론적 증명 (오차 0%) |
소수가 중요한 이유
순수 수학을 넘어 소수는 현대 인터넷과 정보 보안의 든든한 방패 역할을 합니다.
인터랙티브 도표: RSA 암호화 교육용 시연
두 큰 소수의 곱셈이 어떻게 현대 웹 보안의 일방향 자물쇠를 형성하는지 체험해 보세요.
Interactive RSA Key Scale Explorer
Compare toy classroom locks with modern banking encryption scales:
Educational demonstration above uses small numbers (like 35) so every exponent step is visible by hand.
모든 합성수는 소수들을 곱하여 만들 수 있기 때문에 소수는 흔히 "수학의 원자"라고 불립니다. 그러나 그 고유한 대수적 비가역성 덕분에 디지털 시스템 전반에서도 필수불가결한 요소로 쓰입니다.
공개 키 암호화
RSA 암호화, SSH 키 및 TLS 인증서와 같은 보안 프로토콜은 두 개의 큰 소수를 곱하는 것은 쉽지만 그 곱을 소인수분해하는 것은 계산상 불가능하다는 수학적 트랩도어에 의존합니다.
해시 테이블 및 의사 난수 생성기
해시 테이블 크기와 의사 난수 생성기(PRNG)는 해시 충돌을 최소화하고 클러스터링을 방지하며 메모리 버킷을 균등하게 분배하기 위해 소수 모듈러스 연산을 자주 사용합니다.
정수론 및 순수 수학
소수는 리만 가설, 골드바흐 추측, 소수 간격의 분포를 포함하여 과학에서 가장 깊고 풀리지 않은 미스터리의 중심에 있습니다.
정확도, 학술적 출처 및 기술적 한계
동료 평가를 거친 알고리즘, 결정론적 한계, 완벽한 투명성.
Live Browser Engine Self-Test
Verify engine.js directly in your browser against adversarial pseudoprimes, boundaries, and numbers above IEEE-754 float precision.
결정론적 소수성 보장
모든 정수 n < 2⁶⁴ (최대 18,446,744,073,709,551,615)에 대해 당사 엔진은 CP-Algorithms와 Sorenson & Webster가 증명한 7개의 결정론적 밑을 평가합니다. 이 테스트는 확률이 아닌 수학적 증명입니다. 의사소수나 카마이클 수는 절대 통과할 수 없습니다.
메모리 및 연산 한계
일반 계산기 웹사이트는 2⁵³ − 1 (9,007,199,254,740,991) 이상에서 JavaScript IEEE 754 부동소수점 반올림 오차를 겪습니다. 당사 엔진은 원시 숫자 문자열을 임의 정밀도 네이티브 BigInt 타입으로 직접 파싱하여 절단 오차 0%를 보장합니다.
학술 문헌 및 출처
모든 배포는 처음 10,000개의 OEIS 소수, 알려진 합성수 카마이클 함정(561, 1105, 1729, 2465), 메르센 지수, 쌍둥이 소수 및 유클리드 서로소 증명을 다루는 자동화된 단위 테스트 스위트에 대해 검증됩니다.
학술 참고문헌 및 권위 있는 출처
- Crandall, R., & Pomerance, C. (2005): Prime Numbers: A Computational Perspective. 제2판, Springer-Verlag. (밀러-라빈 밑, 폴라드 로 및 Baillie-PSW 테스트에 대한 기초 참고문헌).
- Sorenson, J., & Webster, J. (2015): Strong Pseudoprimes to Twelve Prime Bases. Mathematics of Computation, 85(301), pp. 2489–2503.
- OEIS: 온라인 정수열 사전 (OEIS): 수열 A000040: 소수 (The Prime Numbers).
- GIMPS: Great Internet Mersenne Prime Search (GIMPS): 알려진 가장 큰 소수 기록을 위한 공식 추적기. (2¹³⁶²⁷⁹⁸⁴¹ − 1).
- CP-Algorithms: CP-Algorithms & e-maxx: 결정론적 밀러-라빈 소수 판별 알고리즘.
자주 묻는 질문 (FAQ)
소수와 소수 판별에 관해 가장 자주 묻는 질문들에 대한 수학적이고 명쾌한 답변.
소수(Prime Number)란 무엇인가요?
소수는 1보다 큰 자연수 중에서 1과 자기 자신만을 양의 약수로 가지는 수입니다. 대표적인 예로 2, 3, 5, 7, 11, 13, 97 등이 있습니다.
0과 1은 왜 소수가 아닌가요?
기본적인 수학적 정의에 따라 소수는 정확히 2개의 서로 다른 양의 약수를 가져야 합니다. 1은 약수가 1개뿐이므로 소수가 아닙니다. 0은 0이 아닌 모든 수로 나누어떨어지므로 무수히 많은 약수를 가집니다.
2가 유일한 짝수 소수인 이유는 무엇인가요?
2보다 큰 모든 짝수는 1과 자기 자신 외에도 2로 나누어떨어집니다(예: 4 = 2 × 2, 6 = 2 × 3). 따라서 약수가 3개 이상이므로 모두 합성수입니다. 약수가 정확히 2개인 짝수는 2뿐입니다.
7과 9는 둘 다 소수인가요?
아닙니다. 7은 약수가 1과 7뿐이므로 소수이지만, 9는 약수가 1, 3, 9 세 개이므로 합성수입니다(3 × 3 = 9).
큰 수가 소수인지 어떻게 판별하나요?
작은 수는 제곱근 ⌊√n⌋ 이하의 소수로 나누어 떨어지는지 검사합니다. 64비트 정수의 경우 수학적으로 증명된 7개의 밑을 평가하는 결정론적 밀러-라빈 소수 판별법을 통해 100% 수학적 확실성으로 판별합니다.
가장 큰 소수는 무엇인가요?
가장 큰 소수는 존재하지 않습니다. 기원전 약 300년경 유클리드는 소수가 무한히 많음을 증명했습니다. 현재까지 발견된 가장 큰 소수는 GIMPS 프로젝트에서 발견된 41,024,320자리의 2^136,279,841 − 1입니다.
서로소(Coprime)란 무엇인가요?
두 정수의 최대공약수(GCD)가 1일 때 두 수를 서로소라고 합니다. 각 수가 소수일 필요는 없습니다. 예를 들어 8(2³)과 9(3²)는 둘 다 합성수이지만, gcd(8, 9) = 1이므로 서로소입니다.
1부터 100까지 소수는 몇 개 있나요?
1부터 100 사이에는 정확히 25개의 소수가 존재합니다: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. 이들의 합은 1,060입니다.
카시오 공학용 계산기(fx-991ES)에서 소인수분해는 어떻게 하나요?
지원 모델(Casio fx-991ES PLUS 등)에서 정수를 입력하고 [=]을 누른 뒤, [SHIFT]를 누르고 [FACT] 키를 누르면 화면에 소인수분해 결과가 표시됩니다.