标题: 等差素数列
2,3,5,7,11,13,.... 是素数序列.
类似: 7,37,67,97,127,157 这样完全由素数组成的等差数列, 叫等差素数数列.
上边的数列公差为 30, 长度为 6.
2004 年, 格林与华人陶哲轩合作证明了: 存在任意长度的素数等差数列.
这是数论领域一项惊人的成果!
有这一理论为基础, 请你借助手中的计算机, 满怀信心地搜索:
长度为 10 的等差素数列, 其公差最小值是多少?
注意: 需要提交的是一个整数, 不要填写任何多余的内容和说明文字.
- #include<iostream>
- #include<algorithm>
- #include<string>
- using namespace std;
- const int maxn = 100000000;
- int sha[maxn];
- int su[100000] = { 1,1,0 };
- void shai(int n) {
- int ans = 0;
- for (int i = 2; i < n; i++) {
- if (sha[i])continue;
- su[ans++] = i; // 存一个素数表
- for (int j = i<<1; j <= n; j += i) {
- sha[j] = 1;
- }
- }
- }
- int main() {
- shai(1000000); // 这个不确定, 可以让数大一点
- for (int i = 0; i < 30000; i++) { // 从素数开始 si[i]
- for (int cha = 6; cha < 500; cha++) { // 公差
- int j;
- for (j = 1; j < 10; j++) { // 从素数表里, 开始查找的, 所以 j=0 时, 一定是素数
- if (sha[su[i] + j*cha])break;
- }
- if (j == 10)
- cout << "从素数"<<su[i]<<"开始" << ", 公差为" << cha << endl;
- }
- }
- return 0;
- }
- /* 210 */
来源: http://www.bubuko.com/infodetail-2981019.html