当前位置 博文首页 > m0_51723227的博客：最简单易懂,运算速度也是非常快的C语言筛选
我们知道一个数无论他是素数还是合数,那么他的倍数一定是合数!!!
赞同???
而合数c = 因数a X 因数b
比如16 = 1x16=2x8=4*4;
而[2,4]区间的所有数字的倍数都是合数,剩下的则就是素数了
这里说的是大于1倍,比如3的倍数是6,9…不包括3
eg:
2 4 6 8 10 12 14 16
3 9 12 15
4 16
剩下 3 5 7 11 13 全是质数
同理比如81 = 9 * 9;那么[2,9]的所有数字的倍数都是合数,剩下的就是质数
现在设计这个巧妙的循环
#include<stdio.h>
int a[1000001] = { 0 };
int main()
{
int i, j, n;
for (i = 2; i*i <= n; i++) /*控制在平方区间内*/
for (j = i*i; j <= n; j += i) /*就是这里,保证了某个区间的所有数的所有倍数全是合数,然后赋值为1*/
a[j] = 1;
/*然后在这里设置循环从2开始判断,if(!a[j]),只要是0的值就输出下标,下标就是质数,大家就自己设计了*/
return 0;
}
比如这里牛客网有个题目;
素数数量
C语言用这种解法,你会发现是所有人种最快的;
代码:
#include<stdio.h>
int main()
{
int i,j,n,a[1000001]={0};
for(i=2;i<=1000;i++)
{
for(j=i*i;j<=1000000;j+=i)
a[j]=1;
}
for(i=2;i<=1000000;i++)
{
if(!a[i])
a[i]=a[i-1]+1; /*这两步骤是因为合数全是标记1;从2开始只要是标记为0,就加1;不是就保持和前面一样,不懂的可以自己断点调试,看看数组a怎么在变化*/
else
a[i]=a[i-1];
}
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",a[n]);
}
return 0;
}
