u013421512
coco1312
2015-09-05 15:59
采纳率: 30.2%
浏览 3.3k
已采纳

求教C语言判断素数程序算法,为何j<=sqrt((double)i )??

#include
#include
void fun(int a, int b, int *c)
{ int i,j,d,y;
for (i=3;i<=a/2;i=i+2)
{
/
************found**************/
y=1;

for (j=2;j<=sqrt((double)i );j++)//??为何j<=sqrt((double)i )??
if (i%j==0) y=0;
if (y==1)
{
/*************found**************/
d=a-i;

for (j=2;j<=sqrt((double)d );j++)
if (d%j==0) y=0;
if (y==1)
{*b=i; *c=d;}
}
}
}
void main()
{ int a,b,c;
do
{ printf("\nInput a: ");
_ scanf("%d",&a);}_
while(a%2);
_ fun(a,&b,&c);_
printf("\n\n%d=%d+%d\n",a,b,c);
}
====求教C语言判断素数程序算法,为何j<=sqrt((double)i )??一般不是用j<i来判断是否为素数吗?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

5条回答 默认 最新

  • IZ345654321
    IZ345654321 2015-09-05 16:18
    已采纳

    比如 说i为64,判断它是否为素数,那么j的取值为从2到8(不需要再增加),因为当j从2增加到8,那么i÷j的商(取整)就是当j超过8时的值。当j取2时,商为32,那么j还需要增加到32吗?不需要了,希望你理解

    点赞 评论
  • caozhy

    因为可能有浮点计算的误差,所以最好用小于等于

     j<=(int)sqrt((double)i)
    这样写最好
    
    点赞 评论
  • caozhy
     比如说sqrt(64),按理说应该算出来是8,但是也可能是7.999998(比如说)
    那么j<sqrt((double)i)可能就只能算到6,会少算一个
    
    点赞 评论
  • caozhy
     一个数肯定不能被大于自己平方根的数整除。所以无需判断。
    当然j<i也是对的。至于哪个版本程序效率高,不一定,因为平方根的开销很大,如果是100以内的素数,用平方根所用的时间比节省的那几十次循环要多。
    
    点赞 评论
  • 91program
    91program 2015-09-05 23:37

    C语言计算或比较时,对于不同精度的处理是默认向精度高的数据类型转换。
    所以有时为了取得数值计算的准确度更高,就会使用精度高的数据类型,如上转 double 的实例。

    点赞 评论

相关推荐