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

错误思路

看不懂题。

正确思路

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

CPP

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加判断：

CPP

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

最后输出ans。

正确代码

CPP

#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;
}

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

文章操作

错误思路

正确思路

正确代码

相关推荐

评论

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