UC知道c语言求1-1000素数的算法问题
来源：百度知道 编辑：UC知道 时间：2024/06/08 12:15:06
#include <stdio.h>
#include <math.h>
void main()
{ int n=0, i, j,w,k;
for(i=2;i<=1000; i++)
{w=1;
k=sqrt(i);
for (j=2; j<=k; j++)
if (i%j==0)
{w=0;break;}
if (w)
{
++n;
if (n%10==0) printf("%d\n",i);
else printf("%d\t",i);
}
}
}
这个算法的逻辑思路是怎样的？不懂怎么回事
#include <math.h>
void main()
{ int n=0, i, j,w,k;
for(i=2;i<=1000; i++)
{w=1;
k=sqrt(i);
for (j=2; j<=k; j++)
if (i%j==0)
{w=0;break;}
if (w)
{
++n;
if (n%10==0) printf("%d\n",i);
else printf("%d\t",i);
}
}
}
这个算法的逻辑思路是怎样的？不懂怎么回事
循环嵌套，外层循环是从1-1000的数字i（1排除，这你应该明白），内层是对数字i的素数判断。
素数：除了1和它本身外没有别的因子。也可以理解为：除了1和它本身，其他数来除它余数都不是0。
所以内层循环用从2开始到i的平方根（取整）依次求余，因为到了平方根以后，再增加除数，得到的商是小于平方根的，等于以前取过的除数。所以平方根以后不用再算了。
如果有=0的余数（if（i%j ==0）），说明正在判断的数字不是素数，用break语句退出内层循环；如果没有=0的余数，开关数w不归零，if（w）后的语句执行，计数器n自加一次（找到一个素数），并打印当前检验数i。
打印前有一个if判断，如果计数器n满整10（能够被10整除）就换行，也就是说这个素数表每行10个数。不换行数字键隔一个列表间隔（等于tab）。
根据数学知识可以证明,找一个数的因子只需要从2到sqrt(n){根号下n}就可以了 所以该程序中找素数,j<=sqrt(i);其他应该都可以理解吧
大家都是为了得分吗？