什么是素数?
2, 3, 5, 7, 11, 13, 17, 19, 23, 29…
素数有无穷多个。欧几里得约在公元前 300 年证明。第 1000 个素数是 7919。
素数是大于 1 的整数,它只有两个正因子:1 和它本身。每个大于 1 的整数,要么本身是素数,要么可以唯一地写成素数的乘积。这就是算术基本定理:每个整数都有且只有一种素因数分解。
埃拉托斯特尼筛法:50 以内的素数
欧几里得在约公元前 300 年证明了素数有无穷多个。设想存在一个最大的素数 p。把所有已知素数相乘再加 1,得到的新数要么本身是素数(矛盾),要么有一个不在原列表中的素因子(同样矛盾)。因此素数永远不会结束。
50 以内的素数
| 素数 | # | 素数 | # | 素数 | # |
|---|---|---|---|---|---|
| 2 | 1 | 19 | 8 | 37 | 12 |
| 3 | 2 | 23 | 9 | 41 | 13 |
| 5 | 3 | 29 | 10 | 43 | 14 |
| 7 | 4 | 31 | 11 | 47 | 15 |
| 11 | 5 | 37 | 12 | 53 | 16 |
| 13 | 6 | 41 | 13 | 59 | 17 |
| 17 | 7 | 43 | 14 | 61 | 18 |
PlayMemorize 使用的是从 2 到 7919 的素数,也就是前 1000 个素数。素数定理说明第 n 个素数大约是 n·ln(n)。第 1000 个素数是 7919,和估计值 1000·ln(1000) ≈ 6908 已经相当接近。素数间隙的精细分布则受到黎曼猜想的支配。
欧几里得证明:素数有无穷多个
Assume finitely many primes: p₁, p₂, …, pₙ
N = p₁·p₂·…·pₙ + 1 → N 不被 p₁…pₙ 中的任何一个整除。
因此 N 要么本身是素数,要么含有列表之外的素因子··矛盾。∴ 素数有无穷多个。QED(欧几里得,约公元前 300 年)
哥德巴赫猜想
每个大于 2 的偶整数都可以表示为两个素数之和。例如:4 = 2 + 2,6 = 3 + 3,100 = 3 + 97。它由 Christian Goldbach 在 1742 年写给欧拉的信中提出,虽然已经对所有不超过 4 × 10^18 的偶数完成验证,但至今仍未被严格证明,是数学中最古老的未解问题之一。
素数速览
素数是大于 1 的正整数,它只有两个因子:1 和它本身。欧几里得在约公元前 300 年证明了素数有无穷多个。算术基本定理说明,每个大于 1 的整数都有唯一的素因数分解。素数定理则给出第 n 个素数的大致规模:约为 n*ln(n)。PlayMemorize 训练的是前 1000 个素数(从 2 到 7919)。至于“每个偶数是否都能写成两个素数之和”(哥德巴赫猜想),在提出 280 多年后仍未被证明。
应用领域
数学
✓
物理学
✓
工程学
–
生物学
–
计算机科学
✓
统计学
–
金融
–
艺术
–
建筑学
–
音乐
–
密码学
✓
天文学
–
化学
–
哲学
–
地理学
–
生态学
–
想测试一下你的知识吗?
问题
Euclid如何证明素数有无穷多个?
点击 · 空格键
1 / 10
Topic roundups