[已解决]求素数课后习题不懂

LXMARCO

计算10000里面素数的个数：
int main()
{
        int num,num2;
        int cout = 2;

        for (num = 4; num < 10000; num++)
        {

                for (num2 =1; num2 < num/2; num2++)
                {
                        if (num % num2 == 0)
                                cout++;
                                break;
                        }
                }
        }
        printf("10000以内共有%d个素数\n",10000-cout);
        return 0;
}
请问为什么我这里运行出来的程序10000-cout=2呢？   也就是说cout为9998,每次循环都进如冷if判断为true。如果要改的话怎么改呢？（不使用小甲鱼bool类型的话）
---------------------------------------------以下是小甲鱼的答案（它多用了一个bool类型来辅助判断）-------------------------------------------
#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;
}

最佳答案

月排行榜 / 总排行榜

jackz007

2019-12-24 01:01:08

         一个素数应该是除了 1 和自身外无法枚举到乘法因子的数，所以，判断素数应该循环枚举这个数所有可能的因子，如果此间找到任何一个因子，即可对这个数下否定的判断；相反，如果直到枚举完都无法找到，那才可以最后对这个数下肯定的判断。
        请参考以下代码：

#include <stdio.h>
#include <math.h>

int main()
{
        int num , num2                                                                                      ;
        int cout                                                                                            ;
        for(cout = 0 , num = 2 ; num < 10001 ; num ++) {
                for(num2 = 2 ; num2 < (int) sqrt(num) + 1 ; num2 ++) if(num > num2 && ! (num % num2)) break ;
                if (num2 == (int) sqrt(num) + 1) cout ++                                                    ;
        }
        printf("10000以内共有%d个素数\n" , cout)                                                            ;
}

        与楼主的代码一样，这个代码也设计了两层循环，其中外层循环通过变量 num 从 2 ～ 10000 的范围枚举每一个整数，内层循环通过变量 num2 在 2 ～ (int) sqrt(num)  的范围内扫描当前 num 的乘法因子，如果找到，中途就会通过 break 语句退出循环，这样，事情就变得简单了，只要通过比较内层循环变量 num2 的值，就可以知道循环是否自然结束，如果是，即可判定当前 num 是素数，否则的话，当然就不是。
        编译运行实况：

C:\Bin>g++ -o xp xp.c

C:\Bin>xp
10000以内共有1229个素数

C:\Bin>

跳转到最佳答案楼层

jackz007

         一个素数应该是除了 1 和自身外无法枚举到乘法因子的数，所以，判断素数应该循环枚举这个数所有可能的因子，如果此间找到任何一个因子，即可对这个数下否定的判断；相反，如果直到枚举完都无法找到，那才可以最后对这个数下肯定的判断。
        请参考以下代码：

#include <stdio.h>
#include <math.h>

int main()
{
        int num , num2                                                                                      ;
        int cout                                                                                            ;
        for(cout = 0 , num = 2 ; num < 10001 ; num ++) {
                for(num2 = 2 ; num2 < (int) sqrt(num) + 1 ; num2 ++) if(num > num2 && ! (num % num2)) break ;
                if (num2 == (int) sqrt(num) + 1) cout ++                                                    ;
        }
        printf("10000以内共有%d个素数\n" , cout)                                                            ;
}

        与楼主的代码一样，这个代码也设计了两层循环，其中外层循环通过变量 num 从 2 ～ 10000 的范围枚举每一个整数，内层循环通过变量 num2 在 2 ～ (int) sqrt(num)  的范围内扫描当前 num 的乘法因子，如果找到，中途就会通过 break 语句退出循环，这样，事情就变得简单了，只要通过比较内层循环变量 num2 的值，就可以知道循环是否自然结束，如果是，即可判定当前 num 是素数，否则的话，当然就不是。
        编译运行实况：

C:\Bin>g++ -o xp xp.c

C:\Bin>xp
10000以内共有1229个素数

C:\Bin>

LXMARCO

jackz007 发表于 2019-12-24 01:01
一个素数应该是除了 1 和自身外无法枚举到乘法因子的数，所以，判断素数应该循环枚举这个数所有可 ...

非常感谢！