素数与合数 · 看得见的小蓝本

观察

筛 $2$ 的时候划掉了一大片。接着筛 $3$ ：这一轮新划掉的数里，最小的是几？筛 $5$ 、筛 $7$ 呢？
每一轮新划掉的最小的数总是 $p^{2}$ 。为什么 $2 p$ 、 $3 p$ 这些更小的倍数早就不在了？
筛完 $7$ ，按钮就不让按了。下一个素数是 $11$ ，可是 $1 1^{2} = 121$ 已经超出了 $100$ 。
把 $N$ 调到 $150$ 重新筛。比刚才多用了哪个素数？为什么只多这一个？

大于 $1$ 的整数，如果只有 $1$ 和它自己两个正因数，叫素数（质数）；否则叫合数。 $1$ 两边都不算。

先猜后证

要判断 $223$ 是不是素数，用素数去试除，最多试到哪一个就够了？

7

13

17

111

（它的一半）

先选定答案，才能看到结论。

为什么

“只需要试到 $n$ ” 靠的是下面这个小结论。

合数一定有一个不超过 √n 的素因数

第 1 / 5 步

合数能拆成两个数
设 $n$ 是合数。它有一个不是 $1$ 也不是 $n$ 的因数，于是 $n = ab$ ，其中 $1 < a \leq b$ 。

$n = a \cdot b, 1 < a \leq b$
小的那个不会太大
再取 a 的一个素因数
放到筛子里看
四轮之后

素数用得完吗

筛子可以一直筛下去吗？会不会到某个地方之后，再也没有素数了？

先猜后证

把前六个素数乘起来再加 $1$ ： $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031$ 。它是素数吗？

是素数不是素数

先选定答案，才能看到结论。

练一练

练习 1基础

写出 $40$ 到 $60$ 之间的所有素数。

练习 2基础

$91$ 、 $97$ 、 $119$ 、 $127$ 这四个数里，有几个是素数？

练习 3提高

素数 $p$ 使得 $p + 10$ 和 $p + 14$ 也都是素数。求 $p$ 。

练习 4挑战

求所有正整数 $n$ ，使得 $n^{2} - 8 n + 15$ 是素数。

错误博物馆 · 本站展品

离站之前，看看别人在这里踩过的坑。去博物馆看全部展品 →

展品

把 1 当成素数

1

只能被

1

和它自己整除，所以

1

是素数。

错在哪里？先想一想，再打开

病因　素数要有恰好两个不同的正因数， $1$ 只有一个。更要紧的是：如果 $1$ 算素数， $6 = 2 \times 3 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3$ ，分解就不唯一了。

正整数分三类：

1

；素数（大于

1

，只有

1

和自己两个正因数）；合数。

1

自成一类。

「1 既不是素数也不是合数」

展品

试除只试了 2、3、5

91

是奇数，数字和

10

不被

3

整除，个位不是

0

或

5

，所以

91

是素数。

错在哪里？先想一想，再打开

病因　 $91 \approx 9.5$ ，不超过它的素数有 $2, 3, 5, 7$ ，还差 $7$ 没试。而 $91 = 7 \times 13$ 。

判断

n

是不是素数，要试完所有不超过

n

的素数。

「试到根号为止，一个也不能少」

展品

以为“素数连乘加 1”一定是素数

2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031

不被前六个素数整除，所以它是素数。

错在哪里？先想一想，再打开

病因　 $30031 = 59 \times 509$ 。它只是不被 $2, 3, 5, 7, 11, 13$ 整除，没人保证它不被更大的素数整除。

欧几里得的论证只说：这个数的素因数不在原来的清单里。这已经足够说明清单不完整。

「证明用到什么，就只能说什么」