筛选法求素数
判断100以内的素数有哪些
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int a[100],k=0;
for(int i=2;i<100;i++)
{
a[i]=i;//赋值,一不是素数,所以直接从二开始赋值
}
for(int i=2;i<=100;i++)//判断内层循环里的数能否被1到100内的数整除
{
for(int j=i+1;j<=100;j++)//这一步判断是否是外层循环数的倍数
{
if(a[i]!=0&&a[j]!=0)
{
if(a[j]%a[i]==0)//等于零说明不是素数
{
a[j]=0;
}
}
}
}
for(int i=2;i<=100;i++)
{
if(a[i]!=0)
{
cout<<a[i]<<" ";
}
}
cout<<endl;
return 0;
}
优化一下
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int main()
{
int a[100],k=0;
for(int i=2;i<100;i++)
{
a[i]=i;//赋值,一不是素数,所以直接从二开始赋值
}
for(int i=2;i<sqrt(100);i++)//外层用于限制循环次数
{
for(int j=i+1;j<=100;j++)//用当前i(循环除以之后的元素),如果整除则该数不为素数,否则该数为素数
{
if(a[i]!=0&&a[j]!=0)
{
if(a[j]%a[i]==0)//等于零说明不是素数
{
a[j]=0;
}
}
}
}
for(int i=2;i<=100;i++)
{
if(a[i]!=0)
{
cout<<a[i]<<" ";
}
}
cout<<endl;
return 0;
}
当n的值很大时,如n=10000000;用一下方法
我要寻找从1到15里的素数 (红色代表被筛选掉,不是素数)
第1步:1是素数我不用管,不需要筛选掉1的倍数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
第2步:2没有被前面的筛选掉,所以2是素数,然后筛选掉2的倍数 4 6 8 10 12 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
第3步:3没有被前面的筛选掉,那么3是素数,然后筛选掉3的倍数 6 9 12 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
第4步:4被前面的筛选掉了,不是素数,所以跳过此步骤
第5步:5没有被前面的筛选掉,那么5是素数,然后筛选掉5的倍数 10 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
第6步:6被前面的筛选了,不是素数,所以跳过此步骤
第7步:7没有被前面的筛选掉,那么7是素数,然后筛选掉7的倍数 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
第8步:8被前面的筛选了,不是素数,所以跳过此步骤
第9步:9被前面的筛选了,不是素数,所以跳过此步骤
第10步:10被前面的筛选了,不是素数,所以跳过此步骤
第
11步:11没有被前面的筛选掉,那么11是素数,然后筛选掉11的倍数,11的倍数大于15了,没得筛选
第12步:12被前面的筛选了,不是素数,所以跳过此步骤
第13步:13没有被前面的筛选掉,那么13是素数,然后筛选掉13的倍数,13的倍数大于15了,没得筛选
第14步:14被前面的筛选了,不是素数,所以跳过此步骤
第15步:15被前面的筛选了,不是素数,所以跳过此步骤
所以筛选后的结果中,谁是素数显而易见了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
素数是 1 2 3 5 7 11 13
代码如下
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
//const int n=1e6+10;
int book[101];
int p[101];
int cnt;
int main()
{
cnt=0;
for(int i=0;i<100;i++)
{
book[i]=0;
for(int i=2;i<100;i++)
{
if(!book[i])
{
p[cnt++]=i;
for(int j=i+i;j<100;j+=i)
{
book[j]=1;
}
}
}
}
for(int i=0;i<cnt;i++)
{
cout<<p[i]<<" ";
}
return 0;
}
第二种
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
//const int N 1e6+10;
int p[1000030],ip[100020],sum[1000000];
int k;
int main()
{
k=0;
for(int i=1;i<=1000000;i++)
{
p[i]=0;
}
for(int i=2;i<=1000;i++)
{
if(!p[i])
{
for(int j=2*i;j<=1000000;j+=i)
{
p[j]=1;
}
}
}
for(int i=2;i<1000000;i++)
{
if(p[i])
{
ip[k++]=i;
//cout<<ip[i]<<" ";
}
}
for(int i=2;i<k;i++)
{
cout<<ip[i]<<" ";
}
return 0;
}
上一篇: CSS基础知识21~25