关于sqrt（）函数返回值，以及判断是不是素数问题
例如以下这个例子：#include <stdio.h>
#include <math.h>
int main()
{
int count = 4; // 已知2,3,5,7是素数
int i, j, k;
_Bool flag = 1;
for (i = 9; i < 10000; i++)
{
k = (int)sqrt((double)i);
for (j = 2; j <= k; j++)
{
if (i % j == 0)
{
flag = 0;
break;
}
}
if (flag)
{
count++;
}
else
{
flag = 1;
}
}
printf("10000以内共有%d个素数！\n", count);
return 0;
}
我明白这个为什么只要判断i<=k这个区间的数就可以证明是不是素数，但是9,10,11,12,13,14,15这几个数用sqrt（）函数，返回值不都是3吗？所以这个k怎么判断？因为9,10,12,14,15这几个数不是素数，11,13这两个数是素数，但是它们用sqrt（）函数返回值都是3。 额，你这个不是返回值是不是3的问题，是你没有理解到返回3的含义，你说9，10，12，14，15不是素数，对啊，下面的j从2开始10，12，14可以和2整除，9和15可以和3整除。11，13不是素数，11既不能和2整除也不能和3整除，13也是这样不能整除。所以返回值是3是没有毛病的 只要3不是10的因数，那么4-9 也是不是10的因数 都不用判断了
很明显的一个例子 5是10的因数5>3但是5*2=10 很明显 2已经判断完了，5自然就免了 本帖最后由 jackz007 于 2020-12-26 17:48 编辑
为什么用 sqrt() ，这个问题涉及到因数分解，假设一个数是 64，如果用 2 个因子积的形式来表达，可以是
64 = 2 × 32
64 = 4 × 16
64 = 8 × 8
64 = 16 × 4
64 = 32 × 2
是不是发现一个问题，因为乘法满足交换律，就是说 16 × 4 与 4 × 16 是相等的，这就意味着，如果把一个数所有的因子都找出来判断会多做一遍无用功，事实上，我们只需要判断一半就好了，就是说，对于 64 而言，其因子最多只需要枚举到 sqrt(64) = 8 就足够了。
其实，变通一下，完全可以不用 sqrt() 函数的。都是整数的问题，就用整数来解决。
#include <stdio.h>
int main(void)
{
int i , j , k , count , flag ;
for(count = 0 , i = 2 ; i < 10001 ; i ++) {
for(flag = 1 , j = 2 ; j * j < i + 1 ; j ++) {
if(! (i % j)) {
flag -- ;
break ;
}
}
if(flag) {
if(count) printf("\t") ;
printf("%4d" , i) ;
count ++ ;
}
}
printf("\n") ;
printf("10000以内共有%d个素数！\n", count);
}
页:
[1]