소수 계산기

소수 계산기 - 합계, 개수 & 소수 찾기

🔢 소수의 합을 계산하고, 범위 내 소수를 찾고, 숫자가 소수인지 판별하며, N번째 소수를 구합니다. 시각화가 포함된 빠른 에라토스테네스의 체 알고리즘.

소수란 무엇인가요?

소수는 1보다 큰 자연수 중에서 두 개의 약수(1과 자기 자신)만 갖는 수입니다. 즉, 두 개의 더 작은 자연수의 곱으로 만들 수 없는 수입니다.

처음 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 - 시험 나눗셈(Trial Division):

• n을 2부터 √n까지의 어떤 수로 나눌 수 있는지 확인합니다
• 나누어떨어지면 합성수(소수가 아님)
• 나누어떨어지지 않으면 소수

예: 17은 소수인가요?

• √17 ≈ 4.12 이므로 2, 3, 4로 나누어떨어지는지 확인
• 17 ÷ 2 = 8.5 (나누어떨어지지 않음)
• 17 ÷ 3 = 5.67 (나누어떨어지지 않음)
• 17 ÷ 4 = 4.25 (나누어떨어지지 않음)
• 결과: 17은 소수입니다!

에라토스테네스의 체

n까지의 모든 소수를 찾는 고대 알고리즘:

• 1단계: 2부터 n까지 모든 수를 나열
• 2단계: 2를 소수로 표시하고 2의 배수를 모두 제거
• 3단계: 다음으로 제거되지 않은 수(3)를 소수로 표시
• 4단계: 해당 소수의 배수를 모두 제거
• 5단계: √n까지 반복
• 결과: 제거되지 않은 수가 소수

소수의 합

처음 n개 소수의 합:

• 처음 10개: 2+3+5+7+11+13+17+19+23+29 = 129
• 처음 100개: 합 = 24,133
• 처음 1000개: 합 = 3,682,913

n까지 소수의 합:

• 10까지: 2+3+5+7 = 17
• 100까지: 합 = 1,060
• 1000까지: 합 = 76,127

소수정리(Prime Number Theorem)

n보다 작은 소수의 개수는 대략 n/ln(n)로 근사됩니다:

• 100까지: ~25개 (실제: 25개)
• 1,000까지: ~145개 (실제: 168개)
• 10,000까지: ~1,086개 (실제: 1,229개)
• 100,000까지: ~8,686개 (실제: 9,592개)

소수의 종류

쌍둥이 소수(Twin Primes): 차이가 2인 소수 쌍

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

메르센 소수(Mersenne Primes): p가 소수일 때 2ᵖ - 1 형태

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• 현재 알려진 가장 큰 소수는 메르센 소수(약 2,480만 자리)

소피 제르맹 소수(Sophie Germain Primes): p가 소수이고 2p+1도 소수

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

페르마 소수(Fermat Primes): 2^(2ⁿ) + 1 형태

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65,537
• 현재까지 알려진 페르마 소수는 5개뿐

소수의 활용

암호학(RSA):

• 큰 수를 소인수분해하기 어렵다는 성질을 기반으로 함
• 수백 자리의 큰 소수를 두 개 사용
• 온라인 뱅킹, 이메일, 웹사이트 보안에 사용

해시 테이블:

• 소수 크기의 해시 테이블은 충돌을 줄이는 데 도움이 됨
• 데이터베이스 및 캐싱에 활용

난수 생성:

• 소수는 더 나은 의사난수(pseudo-random) 수열을 만드는 데 도움
• 시뮬레이션과 게임에서 사용

흥미로운 소수 사실

• 무한성: 유클리드(~기원전 300년)가 소수는 끝이 없음을 증명
• 간격(Gaps): 소수가 없는 연속 구간은 얼마든지 길어질 수 있음
• 골드바흐 추측: 2보다 큰 모든 짝수는 두 소수의 합(미해결)
• 리만 가설: 소수 분포에 관한 유명한 난제
• 소수 간격: 연속 소수의 차이는 전반적으로 증가
• 확률: 임의의 n이 소수일 확률은 대략 1/ln(n)

소수 기록

• 가장 큰 알려진 소수: 2^82,589,933 - 1 (2018년, 24,862,048자리)
• 가장 큰 쌍둥이 소수: 2,996,863,034,895 × 2^1,290,000 ± 1
• 계산: GIMPS(Great Internet Mersenne Prime Search) 분산 프로젝트

자주 하는 오해

• 1은 소수가 아님: 현대 정의에서 소수는 약수가 정확히 2개여야 함
• 홀수라고 다 소수는 아님: 9, 15, 21, 25... 는 합성수
• 모든 소수를 만드는 공식: 모든 소수를 생성하는 간단한 공식은 없음
• 소수의 규칙성: 예측 가능한 단순 패턴은 존재하지 않음

💡 팁: 큰 수가 소수인지 확인할 때는 그 수의 제곱근까지만 나눗셈을 검사하면 됩니다! 예를 들어 997이 소수인지 확인하려면 √997 ≈ 31.6 이므로 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31만 테스트하면 됩니다. 어떤 수로도 나누어떨어지지 않으면 소수입니다. 또한 2와 3을 제외한 모든 소수는 6k±1 형태이므로, 탐색을 더 빠르게 만들 수 있습니다!