0%

数论导引读书笔记20191007

素数及复合数

华先生书中,称之为素数与复合数,也就是我们现在称的“质数与合数”。

今将自然数分为三类:

(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}$$之素数整除。

欢迎关注我的其它发布渠道