素数及复合数
华先生书中,称之为素数与复合数,也就是我们现在称的“质数与合数”。
今将自然数分为三类:
(1) 1,只有自然数1为其因数;
(2) p,恰有二自然数1及p为其因数。换言之,p乃大于1且无真因数之自然数;
(3) n,有真因数之自然数。(此类数,有两个以上的因数。)
第二类数名为素数(质数,prime),第三类数名为复合数(合数,composite number)。吾人常以p表素数。
graph LR;
A[自然数]-->B[1];
A-->C[素数p];
A-->D[复合数];
定理1. 非1之自然数皆可分解为素数之积。
证明:略。P.3页
素数
Eratosthenes筛法:若$$n\leq N$$,而$$n$$非素数,则$$n$$必为一不大于$$\sqrt{N}$$之素数整除。