소수 판별기
입력한 숫자가 소수인지 판별하고 인수분해를 수행합니다. 소수의 성질과 활용 사례를 함께 알아보세요.
소수란 무엇인가?
소수(Prime Number)는 1과 자기 자신으로만 나누어지는 1보다 큰 자연수입니다. 예를 들어 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 등이 소수입니다.
🔢 기본 성질
- 2는 유일한 짝수 소수
- 1은 소수가 아님
- 모든 소수는 6n±1 형태 (2, 3 제외)
📊 분포
- 소수는 무한히 많음 (유클리드 증명)
- 숫자가 클수록 소수 간격 증가
- 소수 정리: π(x) ≈ x/ln(x)
🧮 특별한 소수
- 메르센 소수: 2^p - 1
- 페르마 소수: 2^(2^n) + 1
- 쌍둥이 소수: p와 p+2가 모두 소수
에라토스테네스의 체
고대 그리스의 수학자 에라토스테네스가 고안한 소수 찾기 알고리즘입니다. 100까지의 소수를 찾아보세요.
소수 판별 알고리즘
기본 판별법
- 특수 경우 처리: 1은 소수가 아님, 2는 소수
- 짝수 검사: 2 이외의 짝수는 모두 합성수
- 시행 착오법: 3부터 √n까지의 홀수로 나눠보기
- 최적화: 6k±1 형태의 수만 확인
고급 알고리즘
- 밀러-라빈 검사: 확률적 소수 검사
- AKS 검사: 결정론적 다항식 시간 알고리즘
- 페르마의 소정리: a^(p-1) ≡ 1 (mod p)
- 포클링턴 검사: 큰 소수 판별용
소수의 실생활 활용
🔐 암호학
RSA 암호화에서 매우 큰 소수의 곱을 이용합니다. 소인수분해의 어려움이 보안의 근간이 됩니다.
- 공개키 암호화
- 디지털 서명
- SSL/TLS 프로토콜
🎵 음악과 예술
소수는 음계와 리듬에서 독특한 패턴을 만들어냅니다.
- 비주기적 리듬 생성
- 화성 분석
- 작곡에서의 구조적 활용
🔬 과학 연구
물리학과 생물학에서 소수 패턴이 발견됩니다.
- 매미의 생애주기 (13년, 17년)
- 결정학의 대칭성
- 카오스 이론
💻 컴퓨터 과학
알고리즘과 자료구조에서 소수를 활용합니다.
- 해시 테이블 크기 설정
- 의사난수 생성
- 분산 시스템의 노드 분배
미해결 문제들
수학계의 큰 난제들
- 리만 가설: 리만 제타 함수의 비자명한 영점들
- 골드바흐 추측: 모든 짝수는 두 소수의 합
- 쌍둥이 소수 추측: 쌍둥이 소수가 무한히 많은가?
- 크래머 추측: 연속하는 소수 사이의 최대 간격
- 콜라츠 추측: 3n+1 문제와 소수의 관련성
참고: 매우 큰 수의 소수 판별은 시간이 오래 걸릴 수 있습니다. 실제 암호화에서는 확률적 알고리즘을 사용합니다.