UC知道帮忙解释一个C程序
来源：百度知道 编辑：UC知道 时间：2024/06/05 04:02:59
●打表+判断:
就是作一个数表，表中是素数的其值为true,否则，值为false.但要注意效率问题。
bool num[1000001];
memset(num,true,sizeof(num));
for(i=2;i<=500000;i++)
if(num[i])
for(j=2;j<1000000/i;j++)
num[i+j*i]=false;
没看懂...帮忙解释下呗~谢谢哦
就是作一个数表，表中是素数的其值为true,否则，值为false.但要注意效率问题。
bool num[1000001];
memset(num,true,sizeof(num));
for(i=2;i<=500000;i++)
if(num[i])
for(j=2;j<1000000/i;j++)
num[i+j*i]=false;
没看懂...帮忙解释下呗~谢谢哦
首先把数表全都置为true，然后处理不是素数的情况，下标就代表这个数的数值；
如果不是素数，那么肯定可以拆成两个数的乘积（乘数中没有1）即：i*j
而i*j<=1000000 显然，i<500000 j<1000000/i
for(i=2;i<=500000;i++)
if(num[i])
for(j=2;j<1000000/i;j++)
num[i+j*i]=false;
这段的意思就是 从i=2开始，找另外一个乘数j
如i=2,j=2时 num[4]=false;j=3时num[6]=false
为什么要加这个判断：if(num[i]) 是因为如果 num[i]已经是false那么，显然 num[i]已经是某两个数的乘积，如 num[4]已经处理过了，它是2的两倍，所以它不是素数，2的倍数已经处理过了，4的倍数肯定也已经被处理过了；即在已基数为2作处理时，2的倍数值：4、6、8、10、12....都处理过了，那就没有必要再处理一次4的倍数值 4、8、12重复没有必要处理；