首页 > 其他分享 >筛选质数

筛选质数

时间:2023-03-13 21:45:58浏览次数:43  
标签:10 int 质数 删掉 倍数 数组 筛选

 

这一题的思想是这样,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

相关文章