神马品牌网dnf气功是几期勇者:C语言素数问题
来源：百度文库 编辑：神马品牌网 时间：2024/04/19 18:06:16
#include "stdio.h"
#include "math.h"
main()
{int i,j,a[101];
clrscr();
for(i=1;i<=100;i++)
a[i]=i;
a[1]=0;
for(i=2;i<=sqrt(100);i++)
for(j=i+1;j<=100;j++)
{if(a[i]!=0&&a[j]!=0)
if(a[j]%a[i]==0)
a[j]=0;
}
for(i=1;i<=100;i++)
if(a[i]!=0) printf("%d ",a[i]);
}
以上是求100以内的素数的小程序，
为什么if(a[i]!=0&&a[j]!=0)这一句不能省略呢，他又起什么作用呢？
#include "math.h"
main()
{int i,j,a[101];
clrscr();
for(i=1;i<=100;i++)
a[i]=i;
a[1]=0;
for(i=2;i<=sqrt(100);i++)
for(j=i+1;j<=100;j++)
{if(a[i]!=0&&a[j]!=0)
if(a[j]%a[i]==0)
a[j]=0;
}
for(i=1;i<=100;i++)
if(a[i]!=0) printf("%d ",a[i]);
}
以上是求100以内的素数的小程序，
为什么if(a[i]!=0&&a[j]!=0)这一句不能省略呢，他又起什么作用呢？
你可以用筛选法求1000000以内的素数都不会慢
因为你要是取摩运算的话会很慢的,效率非常低
给你主算法
int max = 你想求的范围内素数的算数根,比如100内的就是 max = 根号100
max = (int)sqrt(100);
for(i=0;i<max*max;i++) a[i] = true ;
bool* a = new bool [1000000] ;
for(i=2 ; i<=max ; i++ )
for(j=i*i ; j += i)
a[j] = false ;
for(i=0;i<max*max;i++) if (a[i]) printf("%d",i);
楼主的程序实际上就是素数筛选法的一个实现，只不过有点麻烦。
比如i=2时，j从3到100，把2的倍数筛选掉了。
当i=4时，因为4是2的倍数，4的倍数肯定也是2的倍数，这个内循环实际上可以不用执行了。此时a[4]为0，所以第2个if直接略过了，省去了部分操作，提高了程序效率。
实际上，这个程序还是写麻烦了，if(a[i]!=0&&a[j]!=0)可以直接用if(a[i]==0) continue;代替。
因为这里有个嵌套循环，而且在循环中还设了a[j]=0，那么在下一次进入内循环的时候，如果没有这一句，那么将有可能对0求余了，因为a[j]可能等于0。
其实还有一个效率更高的方法，素数筛选法，具体的网上很多，可以随便找，其思路就是从2开始把素数的倍数去掉，剩下的都是素数了