9.4 素数筛选与区间分析

“数学中的素数有很多有趣的性质，”我说道，”今天我们来找找连续的非素数区间，看看它们有什么规律！”

9.4.1 连续非素数的最大长度

题目描述： 给出一个正整数 n （ 2≤n≤1000000 ），例如 n=30 ，在 1，2，3，…30 中，连续的非素数有: 4 长度为 1 6 长度为 1 8 9 10 长度为 3 其中，最大长度为 5 ，即有连续的 5 个非素数。

输入格式： 一个整数 n 。

输出格式： 一个整数，即连续非素数最大长度。

样例输入：

12

样例输出：

3

代码实现：

#include<bits/stdc++.h>
using namespace std;

bool f[1000010] = {0, 1};  // f[i]=true表示i是非素数，1不是素数
int n;

int main(){
    cin >> n;
    
    // 埃拉托斯特尼筛法标记非素数
    for(int i = 2; i <= n/2; i++){
        for(int j = 2; j * i <= n; j++){
            f[i * j] = 1;  // 标记i*j为非素数
        }
    }
    
    int cnt = 0, ma = INT_MIN;  // cnt当前连续长度，ma最大长度
    
    // 查找连续非素数的最大长度
    for(int i = 1; i <= n; i++){
        if(f[i]){  // 如果是非素数
            cnt++;
            // 检查连续序列是否结束
            if(i == n || !f[i+1]){
                ma = max(ma, cnt);  // 更新最大长度
                cnt = 0;            // 重置计数
            }
        }
    }
    
    cout << ma;
    return 0;
}

算法解析：

1. 使用埃拉托斯特尼筛法标记所有非素数
2. 遍历1到n，统计连续非素数的长度
3. 当连续序列结束时，更新最大长度
4. 输出找到的最大连续非素数长度