[已解决]C语言break和continu的课后作业，求素数第二个for我看不懂是什么意思

BlackWhite_idea

请各位老师，兄弟解答一下

最佳答案

月排行榜 / 总排行榜

jackz007

2021-11-28 11:30:21

         本代码判断素数采用的是排除法，对于每一个 i，先假定它是一个素数，置 flag = 1，然后，在 2 ～ i / 2 的范围内，循环枚举它可能的因子 j，测试 i % j 的余数，如果余数为 0 了，那就说明 j 是 i 的因子， i 就不是一个素数，于是，否定前期 i 是素数的假设，置 flag = 0，结束对 i 的判断；反之，如果在 2 ～ i / 2 的范围内，居然没有一个 j 能使 i % j == 0，那么，说明开头的假设成立，i 确实是一个素数。

         本代码总体由两个循环嵌套构成，第 1 个 for 是为了在 5 ～ 9999 的范围内，枚举出每一个整数 i，而第 2 个 for 是为了在 2 ～ i / 2 的范围内，循环枚举出 i 所有可能的因子 j ，并挨个测试 i % j 的余数是否为 0。所以， i 是否是素数是在第 2 个 for 中做出判断的，这就是第 2 个 for 存在的作用和价值。

          因为乘法满足交换率，所以，枚举 j 的范围可以进一步缩小到 sqrt(i) 像这样

1. for(i = 5 ; i < 10000 ; i ++) {
   
2.         for(j = 2 ; j * j < i + 1 ; j ++) {

复制代码

          此外，除了 2，所有的素数都是奇数，所以，还可以免去对所有偶数的判断，这样，运算效率会提升一倍。

1. for(count = 0 , i = 3 ; i < 10000 ; i ++) {
   
2.         flag = 0                         ;
   
3.         if(i % 2) {
   
4.                 for(flag = 1 , j = 3 ; j * j < i + 1 ; j += 2) {
   
5.                         if(! (i % j)) {
   
6.                                 flag = 0 ;
   
7.                                 break    ;
   
8.                         }
   
9.                 }
   
10.         }
    
11.         if(flag) count ++                ;
    
12. }

复制代码

跳转到最佳答案楼层

嘉岳呀

判断素数的吧

如果它能被其他的书整除，那么就不是素数了

BlackWhite_idea

嘉岳呀 发表于 2021-11-28 10:08
判断素数的吧

如果它能被其他的书整除，那么就不是素数了

我是想问为什么会这么进行运算

番杰

（1）i 相当于 被除数（就是判断它是不是素数）；
（2）j 相当于 除数  （就相当于判断这个j是不是的i的因数，如果i能整除j：那么i就不是素数，反之，i就是素数）

知道以上两点后，就好理解了；
首先j = 2：是因为1本身就是素数的因数，所以没有必要从1开始；
j < i/2 :这里是跟（i/2）比较：相当于优化了算法，写成j<i;
if(i%j == 0):判断这个j是不是的i的因数，如果i能整除j：那么i就不是素数，反之，i就是素数

BlackWhite_idea

番杰 发表于 2021-11-28 10:24
（1）i 相当于 被除数（就是判断它是不是素数）；
（2）j 相当于 除数  （就相当于判断这个j是不是的i的因 ...

j<i/2这一点不是很理解

jackz007

         本代码判断素数采用的是排除法，对于每一个 i，先假定它是一个素数，置 flag = 1，然后，在 2 ～ i / 2 的范围内，循环枚举它可能的因子 j，测试 i % j 的余数，如果余数为 0 了，那就说明 j 是 i 的因子， i 就不是一个素数，于是，否定前期 i 是素数的假设，置 flag = 0，结束对 i 的判断；反之，如果在 2 ～ i / 2 的范围内，居然没有一个 j 能使 i % j == 0，那么，说明开头的假设成立，i 确实是一个素数。

         本代码总体由两个循环嵌套构成，第 1 个 for 是为了在 5 ～ 9999 的范围内，枚举出每一个整数 i，而第 2 个 for 是为了在 2 ～ i / 2 的范围内，循环枚举出 i 所有可能的因子 j ，并挨个测试 i % j 的余数是否为 0。所以， i 是否是素数是在第 2 个 for 中做出判断的，这就是第 2 个 for 存在的作用和价值。

          因为乘法满足交换率，所以，枚举 j 的范围可以进一步缩小到 sqrt(i) 像这样

1. for(i = 5 ; i < 10000 ; i ++) {
   
2.         for(j = 2 ; j * j < i + 1 ; j ++) {

复制代码

          此外，除了 2，所有的素数都是奇数，所以，还可以免去对所有偶数的判断，这样，运算效率会提升一倍。

1. for(count = 0 , i = 3 ; i < 10000 ; i ++) {
   
2.         flag = 0                         ;
   
3.         if(i % 2) {
   
4.                 for(flag = 1 , j = 3 ; j * j < i + 1 ; j += 2) {
   
5.                         if(! (i % j)) {
   
6.                                 flag = 0 ;
   
7.                                 break    ;
   
8.                         }
   
9.                 }
   
10.         }
    
11.         if(flag) count ++                ;
    
12. }

复制代码

番杰

BlackWhite_idea 发表于 2021-11-28 10:34
j

就是一个优化，节省了一半的运行时间：
举一个就比如你判断18是不是一个素数；
j=2时，18可以整除2，也就不需要判断9是不是它的因数了，
一个数的因数一定是成对出现的，就比如18的3和6，2和9；每一对因数都是以i/2为分界线分布的，所以只要判断小于i/2的部分有没有它的因数就行了，有的话对应大于i/2的部分一定也有一个与之对应的因数，反之没的话，就说明他是一个素数