405J1R第七次训练（T635911 最长非质数子段）

pico_fence · 2025-07-20 21:30:00 · 个人记录

错误思路

看不懂题。

正确思路

先来个const int N=5e6+5;再来个bool a[N],然后来个int n,ans,t;在输入n,再来个a[1]=1;然后来个for循环：

for(int i=2;i<=sqrt(n);i++){
    if(a[i]==0){
        for(int j=2;j*i<=n;j++){
            a[i*j]=1;
        }
    }
}

再来个for加判断：

for(int i=2;i<=n;i++){
    if(a[i]==1){
        t++;
    }else{
        t=0;
    }
    ans=max(ans,t);
}

最后输出ans。

正确代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
bool a[N];
int n;
int ans,t;
int main(){
    cin>>n;
    a[1]=1;
    for(int i=2;i<=sqrt(n);i++){
        if(a[i]==0){
            for(int j=2;j*i<=n;j++){
                a[i*j]=1;
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(a[i]==1){
            t++;
        }else{
            t=0;
        }
        ans=max(ans,t);
    }
    cout<<ans;
    return 0;
}