소수,prime_number

1과 자기 자신 이외의 정수로 정수 나눗셈,division이 불가능한 양의 정수 / 자연수.
두 정수 이상의 곱,product으로 표현이 불가. (1, −1 등을 사용한 trivial한 경우는 제외)

작은 것부터 나열하면,
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, …

tbw: 서로소,coprime와 소수의 관계

반대 개념: 합성수,composite_number
{
자연수들의 곱,product자연수,natural_number
(다만 곱하는 수에서 1과 자기 자신은 제외)

소수,prime_number와는 반대 개념

자연수는 1, 소수, 합성수 세 가지로 나눌 수 있음
이것들은 양의 약수의 개수로 명확히 분류됨:
1(양의 약수 한 개), 소수(양의 약수 두 개), 합성수(양의 약수 세 개 이상)

소수는 정수론,number_theory의 주요 주제

합성수는 소인수분해,prime_factorization과정을 통해 소수,prime_number인수,factors들의 곱,product으로 나눌..



합성수를 제외하고 소수만 뽑아내는 방법
// - i.e. 합성수와 소수를 분리하는 방법 - i.e. 어떤 수가 합성수인지 소수인지 여부를 가려내는
primality_test WtEn:primality_test WpSp:Primality_test WpEn:Primality_test - w (소수판정법 소수판별법 ... 아래 section 있음, 나중에 merge)
에라토스테네스_체,Eratosthenes_sieve
...

(tmp; 관련표현 : primality KmsE:primality WtEn:primality NdEn:primality (not in nn) Naver:primality Ggl:primality ) - w

6은 2와 3의 곱으로 이루어져 있으며 이 소수들은 인수(factor), 특히 소인수(prime factor).
// 인수,factor(rel. 인자,factor), esp 소인수,prime_factor(rel. 소인수분해,prime_factorization)
어떤 정수나 자연수를 소수로(즉 소인수로) 분해하는 것을 소인수분해,prime_factorization라고 함.
산술의기본정리?
Fundamental theorem of arithmetic (산술,arithmetic#s-5.1) : Every 자연수,natural_number greater than 1 can be expressed uniquely as the product of primes (up to rearrangement).
This tells us that: 즉 소수는 정수 곱셈의 "atomic elements"이다. (이 정리 때문에 1은 소수로 치지 않는다.)

소수는 정수론,number_theory의 주요 주제

소수 개수의 무한성

개수가 무한하다는 것이 고대에 증명됨.
https://pub.mearie.org/소수의무한성
MathNote:소수의_무한성
Euclid's theorem : There are infinitely many prime numbers.
https://everything2.com/title/Proof that there is no largest prime number

Fermat 소수

$p=2^{2^m}+1\quad(m\ge0)$
m p
0 3
1 5
2 17
3 257
4 65537
이 수열의 수는 소수로 예측되었지만, m=5는 소수가 아님이 밝혀짐. 232+1=4294967297=641×6700417
WpEn:Fermat_number




Mersenne 소수

$p=2^n-1$ (n은 소수)
이 수열도 다 소수가 아니고, Mersenne 수 중에서 소수인 것만 Mersenne 소수로 부름.
현재까지 Mersenne 소수는 대략 51개 발견.
https://everything2.com/title/Mersenne prime

MKL Mersenne_twister (w) { Up: PRNG }

쌍둥이 소수, twin prime

쌍둥이 소수 추측:
$p$$p+2$ 가 모두 소수인 경우가 무한히 많이 존재하는가?

https://everything2.com/title/twin primes

쌍둥이 소수 추측

쌍둥이 소수 추측: 'p, p+2가 모두 소수인 소수쌍(즉 쌍둥이 소수)은 무한히 많다'는 추측,conjecture.


소수계량함수 prime-counting function and 소수 정리 prime number theorem

prime-counting_function or
prime_counting_function
Up: 셈,counting ... tentative pagename : 소수셈함수,prime_counting_function

WpKo:소수_계량_함수
WpEn:Prime-counting_function
https://mathworld.wolfram.com/PrimeCountingFunction.html
counting을 그냥 셈으로 번역하면 안되나? 세기로 번역하면 magnitude가 연상되어 별로임. 소수셈함수,prime_counting_function?
소수개수함수 는 어떨지..

양수 $x$ 에 대해 $x$ 미만의 소수의 수는 대략 $\frac{x}{\ln x}$ 개가 있다는 것이 소수 정리이고,
$\pi(x)=\frac{x}{\ln x}$ 가 소수계량함수.


'소수의 개수' 또는 '소수 세기(counting)' section 만들 것.

2021-12-05 from [https]리만가설 이야기: 에라토스테네스의 체#소수 세기 함수:
소수세기함수: 어떤 수 $n$ 이하인 소수의 개수 $=\pi(n)$
// 근데 이 번역은 세기가 magnitude, strength를 연상시킨다는 단점이.

2023-05-30 via https://horizon.kias.re.kr/24486/
기호 및 그 정의:
2보다 큰 수 $x$ 에 대해, π(x) := x보다 작거나 같은 모든 소수의 개수
Legendre는 x가 커짐에 따라 π(x)가 x/(ln x)에 가까워진다고 추측했다.
이것은 20세기에 가까워져서 증명,proof되어 정리,theorem가 되었다 => 소수정리 prime_number_theorem PNT
(다만 π(x)와 x/(ln x)의 차이,difference가 얼마나 되느냐는 리만_가설,Riemann_hypothesis과 연관되어 아직도 가설,hypothesis로 남아 있다.)


2021-12-29
소수정리,prime_number_theorem,PNT
{
// tmp from https://mathphysics.tistory.com/703 50% 쯤 '소수의 개수' by 기하서 ... at 2022-03-20
{
$x$ 는 1보다 큰 실수.
$\pi(x)\;=\;x$ 보다 작은 소수의 개수

Gauss 시대에는 다음을 추측할 수 있었다. (소수정리)
$\pi(x) \sim \frac{x}{\ln x} \;\; (x\to\infty)$
Gauss는 이것을 증명할 수 없었다.
Riemann은 리만_제타함수,Riemann_zeta_function를 도입하여 어떤 가정 하에 소수정리를 증명할 수 있었다. 리만은 그 가정을 증명하려 했으나 실패했고 현재까지 모든 수학자들이 증명에 실패했다. 그 가정은 리만_가설,Riemann_hypothesis.
}




아이젠슈타인 소수 Eisenstein prime

소수판별법

소수인지 합성수인지 판별하는 것은 중요한 문제... test/method/algorithm.
primality_test - writing

TBD: primality를 primality_test와 별도의 페이지로 만들 필요가 있을지? 아님 '소수' '서로소' 'primality_test' 이 페이지들에서 충분히 설명되므로 필요 없을지.
한다면 pagename? 소수성? 소수여부? ... Naver:primality Google:primality

가장 간단한 것은 trial_division - curr mentioned at 나눗셈,division
등등 수많은 방법


소수 판별 알고리듬,algorithm:
AKS 소수 테스트, Agrawal-Kayal-Saxena
Google:Agrawal-Kayal-Saxena
이것은 소인수분해,prime_factorization와 달리 현실적인 비용으로 가능.