소수 (prime number)
소수(素數, prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수를 의미한다. 예를 들어, 자연수 2, 3, 5의 약수는 1과 자기 자신뿐이기 때문에 자연수 2, 3, 5는 소수라고 할 수 있다. 0.1, 0.2, 0.3 등과 같은 소수(小數)와 구별하기 위해 소쑤라고 읽고, 솟수라고 쓰기도 한다. 소수를 곱하여 여러 합성수를 만들 수 있기 때문에, 모든 수의 '씨앗'이라는 뜻에서, 소수를 씨수라고 부르기도 한다.영어로는 프라임 넘버(prime number)라고 한다. 소수의 반대말은 합성수이다.
개요[편집]
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 산술의 기본 정리의 '1보다 큰 모든 자연수는 그 자체가 소수이거나, 순서를 무시하고 유일한 소인수의 조합을 갖는다'는 내용을 바탕으로 정수론에서는 매우 중요한 주제로 다루어진다. 또한 현대에는 암호 분야에서의 기술적 사용으로 그 중요성이 부각되고 있다. 소수의 개수는 무한하며, 이는 유클리드의 정리에 의하여 최초로 논증되었다. 소수와 합성수를 구분해낼 수 있는 명확한 공식은 지금까지도 밝혀지지 않은 상태이나, 대역적으로 자연수 중 소수의 비율의 근사치를 예측하는 모델로는 여러가지가 알려져 있다. 이러한 방향으로의 연구의 첫 결과는 19세기 말에 증명된 소수 정리인데, 이는 무작위로 선택된 한 수가 소수일 확률은 그 수의 자릿수, 곧 로그값에 반비례함을 알려준다.[1]
역사[편집]
- 유클리드(Euclid)
- 이집트인들의 기록을 살펴보자면 그들이 소수에 대한 약간에 지식이 있었던 것으로 보인다. 예를 들어, 린드파피루스(Rhind papyrus)에는 여러 가지 소수들과 합성 수 들이 쓰여 있었다. 그러나 실질적으로 소수에 관한 연구가 시작된 것은 고대 그리스부터였다. 유클리드가 저술한 원론(기원전 300년)에서는 몇 가지 기본적이고 중요한 증명들이 있는데 예를 들면 소수의 무한성도 그중 하나였다. 또한 유클리드는 메르센 소수(Mersenne prime)로 부터 어떻게 완전수를 만들 수 있는지도 보였다. 에라토스테네스(Eratosthenes)가 고안한 에라토스테네스 체(Sieve of Eratosthenes)는 소수를 찾기에는 가장 간단한 방법이지만 현재 큰 소수를 찾는 컴퓨터는 이 알고리즘을 택하지 않는다. 그리스 이후 17세기까지 소수에 관한 연구는 큰 진보를 하지 않았다.
- 페르마
- 1640년 피에르 데 페르마(Pierre de Fermat)는 그의 이름이 붙은 수많은 정리를 남겼는데, 그중 페르마의 소정리(Fermat's little theorem)는 어떤 수가 소수일 간단한 필요 조건에 대한 정리이다. 페르마는 이 정리를 언급했을 뿐, 정확한 증명을 제시하지 않았으며 후에 라이프니츠(Leibnitz)와 오일러(Euler)에 의해 증명되었다. 참고로 페르마 소정리의 특정 부분은 훨씬 전부터 중국에서도 알려져 있었다. 페르마는 일 때 까지를 검토해 본 후 모든 22ⁿ+1 꼴의 수는 소수일 것으로 추측하였으나 그 54번째 페르마 수인 은, 오일러에 의해 641의 배수임이 밝혀졌다.
- 마린 메르센느(Marin Mersenne)
- 꼴의 소수(p는 소수)는 해당 소수를 연구했던 17세기 프랑스 수학자 마린 메르센느(Marin Mersenne)의 공로에 따라 메르센 소수(Mersenne prime)라는 이름이 붙여졌다. 이는 2의 거듭제곱에서 1을 뺀 수가 소수일 때를 말한다.즉 메르센 소수는 을 만족하는 소수이며, 예를 들어 2²-1=3, 2³-1=7, 2⁵-1=31 등이 해당한다.
- 오일러(Leonhard Euler)
- 오일러의 정수에 대한 연구는 소수에 대해 많은 결과를 낳았는데, 그는 + + + + + ··· 와 같은 형태의 무한 급수가 발산함을 보여, 소수가 무한함을 유클리드와는 다른 방식으로 증명하였다. 또한 오일러는 2p-1(2p-1) 꼴의 수 (이 때, 두번째 항은 메르센느 소수) 들이 모두 유일한 짝수 완전수 꼴 임을 보였다. 하지만 현재까지도 홀수 완전수가 존재하는지 존재하지 않는지에 대한 어떠한 증명도 발견되지 않고 있다.
- 르장드르(Adrien-Marie Legendre)
- 19세기 초에, 르장드르(Legendre)와 가우스(Gauss)는 독립적으로 가 무한대로 발산할 때, 보다 작은 소수의 개수는 와 같다는 사실을 발견하였다. 1859년에 리만은 그의 논문에서 제타 함수(zeta-function)에 대한 아이디어를 선보였다. 리만의 아이디어를 이용하여 1896년 아다마르(Hadamard)와 발레푸생(Vallée-Poussin)은 독립적으로 소수 정리를 증명하였다. 이 후 수학자들은 매우 큰 수에 대하여, 이 수가 소수인지 아닌지 판단할 방법을 모색했다. 이에 따라 1877년에는 페르마 소수들을 위한 Pépin's 테스트, 1878년엔 Proth의 정리, 1856년엔 메르센느 소수들을 위한 Lucas–Lehmer 테스트 등이 발견되었다. 현대에 가장 많이 쓰이는 알고리즘으로는 APRT-CL, ECPP, AKS 등이 있지만 여전히 더 나은 알고리즘을 찾기 위해 많은 수학자가 노력하고 있다. 오랜 시간동안 소수는 순수 수학 외에는 아무 쓸모가 없다고 판단되었으나, 1970년 발명된 RSA 암호 방식을 통해 소수에 대한 생각이 완전히 바뀌게 되었다. [2]
종류[편집]
- 균형잡힌 소수(Balanced primes)
- 그 전 소수와 그 다음 소수의 평균이 소수가 되는 수. 즉, 소수들만 모아놓은 수열 이 있을 때, 을 만족하는 소수 을 균형잡힌 소수라 한다. 예를 들어, 소수 53은 그 전 소수 47과 그 다음 소수 59의 평균이므로 균형잡힌 소수이다. (OEIS의 A006562 번 수열에서 확인 할 수 있다.) 균형잡힌 소수들의 종류로는 5, 53, 157, 173, 211, 257, 263, 373, 563, 593, 607, 653, 733, 947, 977, 1103, 1123, 1187, 1223, 1367, 1511, 1747, 1753, 1907, 2287, 2417, 2677, 2903, 2963, 3307, 3313, 3637, 3733 등이 있다.
- 벨 수 소수(Bell number primes)
- 벨 수는, 수학자 에릭 템플 벨(Eric Temple Bell)의 이름에서 따온 것으로, 조합론에서 n 개의 원소로 구성된 집합을 분할하는 방법을 나타내며, 몇 가지 벨 수는 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975 등이 있다. 이때, 이 벨 수 들 중에서 소수인 것들을 벨 수 소수라 한다. 처음 몇 벨 수 소수로는 2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 등이 있으며, 이는 OEIS 의 A051130 번 수열에서 찾을 수 있다.
- 캐럴 소수(Carol primes)
- 캐럴 소수는 식을 만족하는 소수이다. 캐럴 소수로는 7, 47, 223, 3967, 16127, 1046527, 16769023, 1073676287, 68718952447, 274876858367, 4398042316799, 1125899839733759, 18014398241046527 등이 있다.
- 중앙 십각 소수(Centered decagonal primes)
- 을 만족하는 소수다. 다음 식만 만족하는 수들은 1, 11, 31, 61, 101, 151, 211, 281, 361, 451, 551, 661, 781, 911, 1051, 등이 있으며, 이 들 중, 소수인 것을 바로 십각 수(Centered decagonal number)라 한다. 이 십각 수의 특징은 가운데 구슬이 하나 있고, 그 주위를 10각형이, 그 주위를 20각형이... 이렇게 둘러 쌓아 나아가는 수이다. 중앙 십각 소수는 11, 31, 61, 101, 151, 211, 281, 661, 911, 1051, 1201, 1361, 1531, 1901, 2311, 2531, 3001, 3251, 3511, 4651, 5281, 6301, 6661, 7411, 9461, 9901, 12251, 13781, 14851, 15401, 18301, 18911, 19531 등이 있다.
- 칠각 소수(Centered heptagonal primes)
- 이는 위 중앙 십각 소수와 비슷하지만, 칠각형으로 둘러 쌓아나간다는 점이 다르다. 칠각 수는 식을 만족하는 수를 가리키며, 이들 중 소수들을 칠각 소수라 한다. 칠각 소수는 43, 71, 197, 463, 547, 953, 1471, 1933, 2647, 2843, 3697, 4663, 5741, 8233, 9283, 10781, 11173, 12391, 14561, 18397, 20483, 29303, 29947, 34651, 37493, 41203, 46691 등이 있다.
- 사각 소수(Centered square primes)
- 십각 소수나 칠각 소수와 같지만, 이는 사각형으로 둘러 쌓아나간다는 점이 다르며 의 공식을 만족하는 소수이다. 사각 소수는 5, 13, 41, 61, 113, 181, 313, 421, 613, 761, 1013, 1201, 1301, 1741, 1861, 2113, 2381, 2521, 3121, 3613, 4513, 5101, 7321, 8581, 9661, 9941, 10513, 12641, 13613, 14281, 14621 이 있다.
- 삼각 소수(Centered triangular primes)
- 한 점을 중심으로 삼각형으로 덮어 나갈 때, 만족하는 점의 개수를 삼각수라고 하고, 이 삼각수 중에 소수가 되는 수를 삼각 소수라 할 때, 이는 의 공식을 만족한다. 삼각 소수는 19, 31, 109, 199, 409, 571, 631, 829, 1489, 1999, 2341, 2971, 3529, 4621, 4789, 7039, 7669, 8779, 9721, 10459, 10711, 13681, 14851, 16069, 16381, 17659, 20011, 20359, 23251 등이 있다.[3]
특징[편집]
- 소수는 1보다 큰 자연수이다. 즉, 1은 소수가 아니다.
- 소수의 약수는 1과 자기 자신뿐이다. 즉, 소수의 약수는 2개뿐이며, 역도 성립한다.
- 2는 소수이지만, 2를 제외한 모든 짝수는 2를 약수로 가지므로 소수가 아니다.
- 2, 3을 제외한 모든 소수는 자연수 n에 대해 혹은 꼴이다. 역은 성립하지 않는다.[4]
예제[편집]
- 에라토스테네스의 체(Sieve of Eratosthenes)
- 1~100까지의 모든 소수를 구한다고 가정했을 때,
- 1은 제거
- 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
- 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
- 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
- 지워지지 않은 수 중 제일 작은 7을 소수로 채택하고, 나머지 7의 배수를 모두 지운다.
- 지워지지 않고 남은 수는 전부 소수이다.
12 3 45 67 891011 1213 14151617 1819 20212223 242526272829 3031 323334353637 38394041 4243 44454647 484950515253 545556575859 6061 626364656667 68697071 7273 747576777879 80818283 848586878889 9091929394959697 9899100
void getChe(int num) {
int *arr;
arr = (int *)malloc(sizeof(int) * num);
int i = 2;
// 입력받은 수 만큼 배열에 모두 초기화 해둔다.
for (i = 2; i <= num; i++) {
arr[i] = i;
}
for (i = 2; i <= num; i++) {
if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다.
continue;
for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크
arr[j] = 0;
}
}
// 출력
for (i = 2; i <= num; i++) {
if (arr[i] != 0)
cout << arr[i] << " ";
}
}[5]
- 자바(Java)
public class PrimeNumber1 {
public static void getPrime(int num, ArrayList<Integer> prime) {
prime.add(2);
for (int i = 2; i <= num; i++) {
for (int j = 0; prime.size() > j; j++) {
if (i % prime.get(j) == 0) break; // 소수가 아닌 경우 pass
if (j + 1 == prime.size()) // 소수일 때
prime.add(i);
}
}
for (Integer result : prime) {
System.out.println(result);
}
}
public static void main(String[] args) {
ArrayList<Integer> prime = new ArrayList<Integer>();
long start = System.currentTimeMillis();
getPrime(30000, prime);
long end = System.currentTimeMillis();
System.out.println("수행시간 : " + (end - start));
}
}[6]
- 파이썬(Python)
n=1000
a = [False,False] + [True]*(n-1)
primes=[]
for i in range(2,n+1):
if a[i]:
primes.append(i)
for j in range(2*i, n+1, i):
a[j] = False
print(primes)[5]
각주[편집]
- ↑ 〈소수 (수론)〉, 《위키백과》
- ↑ jjycjn, 〈소수(Prime number) 이야기〉, 《티스토리》, 2016-09-09
- ↑ Psi, 〈여러 가지 소수(Prime number)들〉, 《티스토리》, 2007-12-28
- ↑ 김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09
- ↑ 5.0 5.1 신매력, 〈(C++) 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체〉, 《티스토리》, 2013-09-29
- ↑ 신매력, 〈(JAVA) 소수 구하기 최적의 알고리즘 (1)〉, 《티스토리》, 2013-09-20
참고자료[편집]
- 〈소수 (수론)〉, 《위키백과》</ref>
- 수학방 공식 홈페이지 - https://mathbang.net/199
- 김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09
- 〈2. 소수 구하기 - 에라토스테네스의 체〉, 《위키독스》
- 신매력, 〈(C++) 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체〉, 《티스토리》, 2013-09-29
- 신매력, 〈(JAVA) 소수 구하기 최적의 알고리즘 (1)〉, 《티스토리》, 2013-09-20
- jjycjn, 〈소수(Prime number) 이야기〉, 《티스토리》, 2016-09-09
- Psi, 〈여러 가지 소수(Prime number)들〉, 《티스토리》, 2007-12-28
같이 보기[편집]
이 소수 (prime number) 문서는 수학에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.
| ||||||||||||||||||||||||||||||||||||||||||||||||||
