#소수
소수의 예로는 $2$, $3$, $5$, $179$, $10^9+7$, $10^9+9$ 등이 있습니다.
합성수의 예: $4$, $15$, $2^{30}$.
소수의 또 다른 정의는 다음과 같습니다. $N$의 약수가 정확히 두 개이면 $N$은 소수입니다. 이때 이 약수들은 $1$과 $N$입니다.
#소수의 몇 가지 성질
일반적으로 소수에 대해서는 많은 성질이 알려져 있지만, 그중 거의 대부분은 증명하기가 매우 어렵습니다. 그중 몇 가지는 다음과 같습니다:
- $N$보다 작은 소수는 대략 $\frac{N}{\ln N}$개입니다.
- N번째 소수는 대략 $N\ln N$입니다.
- 소수는 대체로 고르게 분포되어 있습니다. 예를 들어, 어떤 구간에서 소수를 하나 찾아야 한다면 수를 하나씩 확인하며 검사하기만 해도 됩니다 — 수백 개 안에 하나쯤은 반드시 나타납니다.
- 임의의 $N \ge 2$에 대해 구간 $(N, 2N)$에는 항상 소수가 존재합니다(베르트랑 공준)
- 그런데 소수가 하나도 없는 구간은 얼마든지 길게 존재합니다. 그러한 구간을 만드는 가장 간단한 방법은 $N! + 2$부터 시작하는 것입니다.
- 제곱근 시간보다 훨씬 빠르게 수의 소수 여부를 판별하는 알고리즘들이 있습니다.
- 최대 약수 개수는 대략 $O(\sqrt[3]{n})$입니다. 이것은 수학적인 결과가 아니라 순전히 경험적인 결과이므로, 점근 표기에 이것을 쓰지 마십시오.
- 구간 $[1, 10^5]$에 속하는 수가 가질 수 있는 약수의 최대 개수는 128입니다
- 구간 $[1, 10^9]$에 속하는 수가 가질 수 있는 약수의 최대 개수 — 1344
- 구간 $[1, 10^{18}]$에 속하는 수가 가질 수 있는 약수 개수의 최댓값 — 103680
- 과학은 수를 $O(\sqrt[4]{n})$에 소인수분해하는 방법을 알고 있지만, 이에 대해서는 다음 기회에 다루겠습니다.
- 3보다 큰 모든 수는 두 소수의 합으로 나타낼 수 있지만(골드바흐의 추측), 이는 증명되지 않았습니다.