等差素数数列 最长合数段

· · 个人记录

题目：

给定闭区间[a,b] ,要求输出 连续的素数的等差序列,三个以上才算是序列，例如 [100,200] 会输出 151 157 163

再例如输入[1,100] 会有两个等差序列，3 5 7 和47 53 59。输出样式行末的空格保留。 a和b均小于10000

生成素数的方法很值得记录

还要注意一个小坑：特殊数字7829

7817 7823 7829

7829 7841 7853

两个数列，按题目的理解，它似乎是不用重复的数字，因此删去了第二个数列，但这一点没有在题目中说明，很坑。以下是允许重复的代码（懒得改了）

#include <iostream>
#include <cstdio>
#include <vector>
#define maxn (10010)
using namespace std;

int number[maxn];
vector<int> vec;

int main() {
    for (int i = 2; i < maxn; i++) {
        if (number[i] == 1) continue;
        for (int j = i; ; j++) {
            int re = i * j;
            if (re >= maxn) break;
            number[re] = 1;
        }
    }
    for (int i = 2; i < maxn; i++) {
        if (number[i] == 0) 
            vec.push_back(i);
    }

    int a, b;
    scanf("%d%d", &a, &b);
    for (int i = 0; i < vec.size(); i++) {
        int count = 0;
        if (vec[i] < a) continue;
        if (vec[i+2] > b) break;
        if (vec[i + 1] - vec[i] == vec[i + 2] - vec[i + 1]) {
            count = 3;
            printf("%d %d %d ", vec[i], vec[i + 1], vec[i + 2]);
            while (1) {
                i++;
                if (vec[i + 2] > b) break;
                if (vec[i + 1] - vec[i] == vec[i + 2] - vec[i + 1]) {
                    printf("%d ", vec[i + 2]);
                }
                else {
              // 若要满足要求，加上i++; 即可
              break;
           }
            }
            printf("\n");
        }
    }
    return 0;
}

最长合数段

给定区间[a,b],输出这个区间里最长的连续合数段，a和b均小于等于10000

#include <iostream>
#include <cstdio>
#include <vector>
#define maxn (10010)
using namespace std;

int number[maxn];
vector<int> vec;

int main() {
    for (int i = 2; i < maxn; i++) {
        if (number[i] == 1) continue;
        for (int j = i; ; j++) {
            int re = i * j;
            if (re >= maxn) break;
            number[re] = 1;
        }
    }

    int a, b;
    scanf("%d%d", &a, &b);
    int start = 0, length = 0;
    for (int i = a; i <= b; i++) {
        if (number[i] == 1) {
            int startNow = i, lengthNow = 1;
            while (number[++i] == 1 && i <= b) {
                lengthNow++;
            }
            if (lengthNow > length) {
                start = startNow;
                length = lengthNow;
            }
        }
    }
    for (int i = 0; i < length; i++) {
        printf("%d ", i + start);
    }   
    return 0;
}