Question

c语言编程，求素数的问题

题目：求100之内的素数
1.程序分析：
2.程序源代码：
#include <stdio.h>
#include "math.h"
#define N 101
main()
{
int i,j,line,a[N];
for(i=2;i<N;i++) a[i]=i;
for(i=2;i<sqrt(N);i++)
for(j=i+1;j<N;j++)
{
if(a[i]!=0&&a[j]!=0)
if(a[j]%a[i]==0)
a[j]=0;}
printf("\n");
for(i=2,line=0;i<N;i++)
{
if(a[i]!=0)
{printf("%5d",a[i]);
line++;}
if(line==10)
{printf("\n");
line=0;}
}
}

就这步 if(a[i]!=0&&a[j]!=0) 我非常不理解，为什么要都非等于0？这程序去掉这一步就不能算，前面不是输入a[i]和a[j]的值都没有0的嘛？为什么还要在说明非等于0？有没大虾帮忙加一下注释或者解释一下为什么
if(a[i]!=0&&a[j]!=0) 经过我的思考，我发现a[j]!=0的确有用，但是在前面开始的时候没用到，是后面语句if(a[j]%a[i]==0) a[j]=0;使用以后才可能出现a[j]=0的情况，但是a[i]好像在这里面怎么样都不可能为0啊。。很是不理解啊

Answer 1

他这样是筛素数
a[i]最初等于2 他把能被2整除的都记为0了
那在以后的运算中 保证a[i]是素数 也就是除一个素数
a[j]等于0 说明他已经被一个素数整除了 已经不是素数了
所以就不用再计算他了
也就是 先筛掉2的倍数
再筛掉3的倍数
再筛掉5的倍数（4被2整除 已经记为0）
再筛掉7的倍数（6被2整除 已经记为0）
再筛掉11的倍数 （8被2整除 9被3整除 10被2整除 都已经被记为0）
。。。。。
最后剩下的就都是素数了

楼主主要注意一下i和j的循环
j的循环是在i的循环里面的，而且他们同是代表数组a的下标
那么当i=2时，是进入j的循环，此时是要将j的循环跑完之后才再进行i++
那么a[j]已经记为0的数，也就是j，i的循环肯定是之后才会循环到
再说明白点，当i=2时，你把j=4的a[j]=0，那么此时的i是2，之后i会自加到4
那么a[i]就是0
如果楼主想不明白
可以把i和j的循环打出来看一下，就像这样
for(i=2;i<sqrt(N);i++)
for(j=i+1;j<N;j++)
{
printf("i=%d j=%d\n",i,j);
if(a[i]!=0&&a[j]!=0)
if(a[j]%a[i]==0)
a[j]=0;
}

Answer 2

for(i=2;i<sqrt(N);i++)
for(j=i+1;j<N;j++)
{
if(a[i]!=0&&a[j]!=0)
if(a[j]%a[i]==0)
a[j]=0;}//这步会把某些值变为0
i和j是 同一个数组的下标，你用了两重循环，a[j]=0，把a数组某些值赋值为0之后，通过i访问a数组的元素，就可能访问到这些0

Answer 3

对不

Answer 4

if(a[i]!=0&&a[j]!=0) 这一句确实是前面a[i]和a[j]的值都没有0.我个人认为是为if(a[j]%a[i]==0)
a[j]=0;}
printf("\n");
这几句做前提的.供参考.