自动搬运

查看原文

来自洛谷，原作者为

	HsKr Coming home

搬运于2025-08-24 22:13:53，当前版本为作者最后更新于2020-02-04 22:40:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

UPDATE

2020-02-05 将速度是1/3改为3倍，感谢Stay_Hungry

其实不需要素数筛，不需要存入数组，一个素数判断就够了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
bool isprime(int x){//判断是否素数
	if(x<=1) return false;//如果小于2，一定不是素数
	for(int i=2;i<=sqrt(x);i++){//为什么要到sqrt(x)呢，因为如果有一个大于sqrt(n)的数可以被n整除，那么必有一个数n/i也可以被n整除且小于i
		if(x%i==0) return false;//如果可以整除，那么不是素数
	}
	return true;//是素数
}
int main(){
	int n,a;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		if(isprime(a)){
			cout<<a<<" ";//是素数，就输出
		}
	}
	return 0;
}

其实还可以优化，这里有一个优化的代码，速度是上面的$3$倍，可以看一看

bool isprime(int n){
    if(n<=1) return false;
    if(n==2||n==3) return true;
    if(n%6!=1&&n%6!=5) return false;
    for(int i=5;i*i<=n;i+=6) if(n%i==0||n%(i+2)==0) return false;
    return true;
}

除2,3外，其他所有素数都必须是$6n+1$或$6n+5$，因为$6n+2=2(3n+1)$，$6n+3=3(2n+1)$，$6n+4=2(3n+2)$，都有非1和本身因数，不是素数