您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记

c语言算法杂谈-for循环结构-质数算法解析

发布时间：2021-04-12 21:27:23编辑：雪饮阅读（）

 这里要实现对从2-100的质数进行判断，并输出都有哪些数是质数。既然谈到了算法层面，那么自然不是简单的暴力循环。

那么具体的实现如：
#include <stdio.h>
int main()
{
 
 int i, j;
   for(i=2; i<100; i++) {
    /*
       j <= (i/j):
              假如这里要判断i是否是质数
              那么这个i的最大因数在i自己，最小因数就是1
              所以内部循环最大范围就是1-i
              假设i的值就是35
              由于是从2开始判断，
              与2进行乘法运算得到35:
                     2*17+1=35
                     3*11+2=35
                     4*8+3=35
                     5*7=35
              可见左因数越大，右因数越小
              那么为了减少循环次数，比如这里2*17+1=35计算了就不需要再次计算17*2+1=35
              以此类推：
                     3*11+2=35计算了就不需要再次计算11*3+2=35
                     4*8+3=35计算了就不需要再次计算8*4+3=35
                     5*7=35计算了就不需要再次计算7*5=35
              可见内部循环实际有效次数就是每次计算时获得的右因数，不可能大于这个右因数，只能在这个右因数范围内
              这里假设左因数为j，则右因数(每次最大范围)为i/j（向下取余，不够一次若向上则会导致超过i的值，比如这里18就是36了，则肯定是无效的一次）
    */
      for(j=2; j <= (i/j); j++){
          printf("child:i:%d,j:%d,i/j:%d,i%j:%d\n", i,j,(i/j),i%j);
          //只要有一个能整除的，那么当前i不是质数
          if((i%j)==0) {
                 break;
          }
      }
       printf("i:%d,j:%d,i/j:%d\n",i,j,(i/j));
       /*
              j > (i/j):
                     这里要以当前左因数大于右因数来做为当前待判断质数i是否为质数的依据呢？
                     情况1：
                     首先从上面的规律我们可以知道，左因数一开始是小于右因数的
                     如果一个数不是质数，则通过左因数就能判断了，比如6是合数，那么通过2*3=6的2就能判断了，没有必要还要进行3*2的判断。
                     那么上面程序break的条件就正好是合数时候才break，那么break侯j++就不能被执行了（这里需要注意的就是for循环的第三个条件语句，如这里的j++,他是在一个循环体每论循环结束才开始调用的）
                     而j又是左因数，所以说通过左因数大于右因数就能立判是否为质数。
                     像是上面35的情况，若不加那个break，则接下来执行如：
                     5*7=35
                     6*5+5=305
                     7*5=35
                     8*4+3=35
                     但是即便如此还有j <= (i/j)的限制，所以这里的逻辑5*7=35之后就没有继续执行了
                     情况2：
                     那么还有另外一种情况就是比如25这种合数，虽然他有5*5=25这种左右因数相同的情况，但是这个也会在上面break的时候被跳出，那么左右因数还是相等的，因为
                     j++不会自增了，就保持在左右因数相等的情况
                     所以这里j>(i/j)才是最终判断当前数i是否为质数的依据。
                    
                     那么再看一个是标准质数的情况，比如37：
                     他的执行流程就是：
                     2*18+1=37
                     3*12+1=37
                     4*9+1=37
                     5*7+2=37
                     6*6+1=37
                     7*5+2=37(根据循环条件j <= (i/j)，所以这一步不会执行，但是上一步6*6时候循环体正常循环结束，j++了，所以此时也是左因数大于右因数，只是这一步不用执行而已)
       */
      if(j > (i/j)) printf("%d is Prime number\n", i);
   }
}