社区讨论

线性筛80分，最后两个re

ttamamocross
P3912素数个数参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo7sqx1i
此快照首次捕获于
2023/10/27 07:09
2 年前
此快照最后确认于
2023/10/27 07:09
2 年前
查看原帖
rt，本蒟蒻开1e8的数组时就会全MLE，开1e7时最后两个点就会过不了
CPP
#include<iostream>
#include<iostream>
#include<cstring>

using namespace std;
const int MAX=1e7+1;
int a[MAX],prime[MAX];
int main(){
	int n,m=0;
	cin>>n;
	memset(a,0,sizeof(a)); 
	for(int i=2;i<=n;i++){
		if(a[i]==0){
			a[i]=i;
			prime[++m]=i;
		}
		for(int j=1;j<=m;j++){
			if(prime[j]>a[i]||prime[j]>n/i)break;
			a[i*prime[j]]=prime[j];
		}
	}
	cout<<m; 
}

回复

共 3 条回复，欢迎继续交流。

正在加载回复...