在线学习
重点科目
初中数学
高中数学
高等数学
线性代数
概率统计
高中物理
数学公式
主要科目
复变函数
离散数学
数学分析
实变函数
群论
数论
未整理科目
近世代数
数值分析
常微分方程
偏微分方程
大学物理
射影几何
微分几何
泛函分析
拓扑学
数学物理
趣味数学
科数网
首页
教材
高考区
考研区
VIP
科数网
题库
在线学习
高中数学
高等数学
线性代数
概率统计
高中物理
复变函数
离散数学
你好
游客,
登录
注册
在线学习
数论
素数及其判别法
最后
更新:
2023-11-09 18:30
查看:
250
次
反馈
刷题
素数及其判别法
**素数及其判别法** 考察正整数的正因数, 我们发现, 有的正整数仅有一个正因数 (如 1), 有的正整数仅有两个正因数(如 $3,13,31$ ), 而有的正整数至少有三个正因数(如 $12,14,81$ ). 我们把仅有两个正因数的正整数叫做素数, 不是素数又不是 1 的正整数叫做合数. 由定义知, $3,13,31$ 是素数, $12,14,81$ 是合数, 1 既不是素数, 也不是合数. 显然, 2 是惟一的偶素数, 也是最小的素数. 每个合数总可以表示成两个大于 1 的正整数的乘积, 而素数则不能. 观察 找出下列每个正整数的正因数: $$ 6,7,9,21,65,77,121 . $$ 观察每个正整数除 1 外的最小的一个正因数, 从中你能发现什么规律? 我们发现, 每个正整数 $n$ 除 1 外的最小正因数 $p$ 是一个素数. 事实上, 假设 $p$ 不是素数, 因为 $p>1$, 所以 $p$ 为合数, 那么 $p$ 必然有 $1, p$ 以外的正因数 $q$, 使得 $q \mid p$. 因为$p \mid n$, 所以 $q \mid n$, 于是 $q$ 是 $n$ 的除 $1, p$ 以外且小于 $p$ 的正因数, 这与已知矛盾, 故最小正因数 $p$ 是一个素数. 一般地, 任何大于 1 的整数, 总存在一个素数因数. 通常, 把一个正整数的素数因数叫做它的素因数. 对大于 1 的整数 $n$, 如果 $n$ 不是素数, 我们可以将 $n$ 分解为一个素数和某个大于 1 的整数 $a$ 的乘积, 如果 $a$ 是一个素数, 则过程停止. 否则, 又可将 $a$ 分解为一个素数和某个大于 1 的整数 $b$ 的乘积. 对 $b$ 又分两种情形: 若 $b$ 为素数, 则过程停止; 若 $b$ 不是素数, 则将 $b$ 继续分解为一个素数和某个大于 1 的整数 $c$ 的乘积. 如此进行下去, 直到过程停止, 最后总可将 $n$ 分解为一些素数的乘积. 例如, $12=2 \times 2 \times 3,78=2 \times 3 \times 13$. 既然任何大于 1 的整数 $n$ 总可分解为一些素数的乘积, 那么素数有多少个? 有限还是无限? 为什么? 我们不妨假设素数有有限个, 即 $m_1, m_2, m_3, \cdots, m_k$, 记这 $k$ 个素数的乘积为 $N$, 即 $$ N=m_1 m_2 m_3 \cdots m_k \text {. } $$ 由此可知, 任意一个素数 $m_i(i=1,2, \cdots k)$ 都整除 $N$, 但不能整除 $N+1$. 又由于 $N+1$ 为大于 1 的正整数, 所以它一定能被某个素数整除, 这就产生了矛盾. 因此, 假设素数有有限个是错误的, 素数有无穷多个 对给定的大于 1 的正整数, 如何判断它是不是素数呢? 例如, 要判断 61 是不是素数, 是否需要用 $2 \sim 60$ 之间的数- - 试除 61 呢? 没有必要. 因为 2 不是 61 的因数, 那么 2 的倍数也不是 61 的因数. 同样地, 若 3 不是 61 的因数, 那么 3 的倍数也不是 61 的因数. 这就是说只需用 $2 \sim 60$ 之间的素数试除 61 即可. 另一方面, 如果 61 是合数, 那么它一定可以表示成两个大于 1 的正因数的乘积, 其中较小的一个正因数一定不超过 $\sqrt{61}$, 并且它的素因数也是 61 的素因数. 这就是说, 如果 61 是合数, 那么它一定存在不超过 $\sqrt{61}$ 的素因数. 因此只需用 $2 \sim 60$ 之间不超过 $\sqrt{61}$ 的素数试除 61 即可. 不超过 $\sqrt{61}$ 的素数为 $2,3,5,7$, 由于它们都不整除 61 , 所以 61 是素数. 一般地, 我们有下面的判别法: 如果大于 1 的整数 $a$ 不能被所有不超过 $\sqrt{a}$ 的素数整除, 那么 $a$-定是素数. 这个判别法实际上给出了一种寻找素数的有效方法. 例 3 找出 $1 \sim 100$ 中的全部素数. 解:只需把 1 与 $1 \sim 100$ 之间的合数去掉即可. 而对于 $1 \sim 100$ 之间的每个合数 $a$, 它一定能被某个不超过 $\sqrt{a}$ 的素数整除, 从而能被不超过 $\sqrt{100}=10$ 的素数整除. 我们知道,不超过 10 的素数为 $2,3,5,7$. 在 $1 \sim 100$ 中首先去掉 1 , 然后分别去掉 $2,3,5,7$ 除自身以外的倍数, 最后剩下的数就是不超过 100 的全部素数. 具体做法如下表:  因此不超过 100 的素数为 $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$, 共 25 个. 这种寻找素数的方法叫做埃拉托斯特尼 (Eratosthenes) 篮法.
开VIP会员
非会员每天6篇,会员每天16篇,VIP会员无限制访问
题库训练
自我测评
投稿
上一篇:
带余除法
下一篇:
最大公因数与最小公倍数
本文对您是否有用?
有用
(
0
)
无用
(
0
)
纠错
高考
考研
关于
赞助
公式
科数网是专业专业的数学网站。