[已解决]关于sqrt（）函数返回值，以及判断是不是素数问题

You-Name

例如以下这个例子：

#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。

最佳答案

月排行榜 / 总排行榜

严凯

2020-12-26 16:56:50

额，你这个不是返回值是不是3的问题，是你没有理解到返回3的含义，你说9，10，12，14，15不是素数，对啊，下面的j从2开始10，12，14可以和2整除，9和15可以和3整除。11，13不是素数，11既不能和2整除也不能和3整除，13也是这样不能整除。所以返回值是3是没有毛病的

跳转到最佳答案楼层

严凯

额，你这个不是返回值是不是3的问题，是你没有理解到返回3的含义，你说9，10，12，14，15不是素数，对啊，下面的j从2开始10，12，14可以和2整除，9和15可以和3整除。11，13不是素数，11既不能和2整除也不能和3整除，13也是这样不能整除。所以返回值是3是没有毛病的

wp231957

只要3不是10的因数，那么4-9 也是不是10的因数 都不用判断了
很明显的一个例子   5是10的因数  5>3  但是5*2=10   很明显 2已经判断完了，5自然就免了

jackz007

        为什么用 sqrt() ，这个问题涉及到因数分解，假设一个数是 64，如果用 2 个因子积的形式来表达，可以是

1. 64 = 2 × 32
   
2. 64 = 4 × 16
   
3. 64 = 8 × 8
   
4. 64 = 16 × 4
   
5. 64 = 32 × 2

复制代码

       是不是发现一个问题，因为乘法满足交换律，就是说 16 × 4 与 4 × 16 是相等的，这就意味着，如果把一个数所有的因子都找出来判断会多做一遍无用功，事实上，我们只需要判断一半就好了，就是说，对于 64 而言，其因子最多只需要枚举到 sqrt(64) = 8 就足够了。
       其实，变通一下，完全可以不用 sqrt() 函数的。都是整数的问题，就用整数来解决。

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int i , j , k , count , flag              ;
   
6.         for(count = 0 , i = 2 ; i < 10001 ; i ++) {
   
7.                 for(flag = 1 , j = 2 ; j * j < i + 1 ; j ++) {
   
8.                         if(! (i % j)) {
   
9.                                 flag --           ;
   
10.                                 break             ;
    
11.                         }
    
12.                 }
    
13.                 if(flag) {
    
14.                         if(count) printf("\t")    ;
    
15.                         printf("%4d" , i)         ;
    
16.                         count ++                  ;
    
17.                 }
    
18.         }
    
19.         printf("\n")                              ;
    
20.         printf("10000以内共有%d个素数！\n", count);
    
21. }

复制代码