这一题的思想是这样,1,2,3,4,5,6,7,8,9,10.遍历数组,先把i的倍数全部删掉,因为如果是谁的倍数那么肯定就不是质数,把所有的倍数都删掉以后,剩下的就是质数了。比如,1肯定不是质数了,2的倍数是4,删掉4,3的倍数是6,是9,删掉6,9,4的倍数是8,删掉8,5的倍数是10,删掉10,剩下的是3,5,7,这个数组里质数只有这三个没有被删掉,可以设计一个标记数组避免重复删除。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
bool st[N];//记录是否是质数,避免重复删除,不是质数的话是true
int primes[N];//记录所有的质数的数组
int cnt;//记录质数的个数
void isprimes(int n){
for(int i=2;i<=n/i;i++){
if(!st[N]){//如果数组没有被标记为true
primes[cnt++]=i;//则是质数
}
for(int j=i+i;j<=n;j+=i){//删除i的倍数
st[j]=true;
}
}
int main(){
int n;
cin>>n;
isprimes(n);
cout<<cnt<<endl;
return 0;
}
标签:10,int,质数,删掉,倍数,数组,筛选 From: https://www.cnblogs.com/chenxinyue/p/17212994.html