设 n 是 一 个 正 整 数 ， 如 果 对 于 所 有 素 数 p ≤ n , 都 有 p ∤ n , 则 n 一 定 是 素 数 。 设n是一个正整数，如果对于所有素数p\le \sqrt{n},都有p\nmid n,则n一定是素数。 设n是一个正整数，如果对于所有素数p≤n ,都有p∤n,则n一定是素数。 证 明 ： 证明： 证明： 反 证 法 ： 假 设 n 是 一 个 合 数 ， 它 的 最 小 正 因 数 为 k ， 则 k ∣ n , 我 们 现 在 只 需 要 证 明 k 是 素 数 且 k ≤ n , 那 么 我 们 就 找 到 了 一 个 素 数 k 不 满 足 定 理 的 条 件 。 反证法：假设n是一个合数，它的最小正因数为k，则k\mid n,\\ 我们现在只需要证明k是素数且k\le \sqrt{n},那么我们就找到了一个素数k不满足定理的条件。 反证法：假设n是一个合数，它的最小正因数为k，则k∣n,我们现在只需要证明k是素数且k≤n ,那么我们就找到了一个素数k不满足定理的条件。
k 是 素 数 ： 因 为 我 们 已 经 假 设 了 k 是 最 小 正 因 数 ， 如 果 k 是 合 数 ， 那 么 有 q ∣ k , 又 k ∣ n , 所 以 q ∣ n , 那 么 k 就 不 是 最 小 正 因 数 了 ， q 成 了 最 小 正 因 数 ， 与 假 设 矛 盾 。 k是素数：因为我们已经假设了k是最小正因数，如果k是合数，那么有q\mid k,又k\mid n,所以q\mid n,那么k就不是最小正因数了，q成了最小正因数，与假设矛盾。 k是素数：因为我们已经假设了k是最小正因数，如果k是合数，那么有q∣k,又k∣n,所以q∣n,那么k就不是最小正因数了，q成了最小正因数，与假设矛盾。 k ≤ n ： 我 们 可 以 将 n 表 示 成 n = k d , 0 < k ≤ d < n , 因 为 k 乘 比 自 己 大 的 数 等 于 n ， 那 么 k 乘 自 己 应 该 小 于 等 于 n ， 即 k 2 ≤ n → k ≤ n k\le \sqrt{n}：我们可以将n表示成n=kd,0<k\le d<n,\\ 因为k乘比自己大的数等于n，那么k乘自己应该小于等于n，\\ 即k^{2}\le n\rightarrow k\le \sqrt{n} k≤n ：我们可以将n表示成n=kd,0<k≤d<n,因为k乘比自己大的数等于n，那么k乘自己应该小于等于n，即k2≤n→k≤n 综 上 ， 证 明 结 束 综上，证明结束 综上，证明结束
