论坛 › C\C++交流 › 求素数课后习题不懂

LXMARCO 发表于 2019-12-24 00:35:03

求素数课后习题不懂

计算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

本帖最后由 jackz007 于 2019-12-24 02:18 编辑

         一个素数应该是除了 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 发表于 2019-12-24 04:08:29

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

非常感谢！

查看完整版本: 求素数课后习题不懂