求100至200间的全部素数

wsb1991abc

#include<stdio.h>
#include<math.h>
int main()
{
  int m,n=0,k,q;
  for(m=101;m<=200;m=m+2)
  {
          q=sqrt(m);
          for(k=2;k<=q;k++)
                  if(m%k==0)
                break;
                  if(k>=q+1)
                  {
                          printf("%d\t",m);
                      n++;
                  }
                  if(n%6==0)
                          printf("\n");
  }
  return 0;
}
这个程序的第12行有些看不懂,K与q+1的比较前面应该有M与K相除取余的关系叙述,现在的语句并没有说明K与q+1的关系,只比较大小有什么 用?

FishC

你的思路基本正确，可以使用一个嵌套循环来找出100至200之间的所有素数。不过你的代码中存在一些错误，比如没有包含正确的头文件，并且在判断素数时的循环条件有误。

下面是修改后的代码：

++
#include <iostream>

using namespace std;

int main() {
    int m, n = 0;
    for (m = 100; m <= 200; m++) {  // 循环100至200之间的数字
        bool isPrime = true;  // 标记当前数字是否为素数
        for (int i = 2; i < m; i++) {  // 判断当前数字是否能被除了1和自身外的其他数字整除
            if (m % i == 0) {
                isPrime = false;  // 如果能被整除，则不是素数
                break;
            }
        }
        if (isPrime) {  // 如果当前数字是素数，则输出
            cout << m << " ";
            n++;
            if (n % 10 == 0) {  // 每输出10个素数换行一次
                cout << endl;
            }
        }
    }

    return 0;
}

运行这段代码，你将会得到一个输出结果，其中包含了100至200之间的全部素数。注意，为了使输出更加美观，我设置了每输出10个素数就换行一次。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

Gordon1

比较大小是因为当k大于或等于m的算术平方根，并且前面没有数可以被整除从而跳出循环，就可以确定它是素数了，所以就只需要比较大小即可

jackz007

    要判定一个数 M 是否是素数，一般需要用 M 去除以 2 ~ M - 1 之间所有的数，看看是否能找到某一个整除因子来进行判定，比如，要判定 12 是否是素数，那就需要用 12 分别去除以 2、3、4、5、6、7、8、9、10、11，我们知道，乘法满足交换律，如果 M = a x b，那么，a 和 b 都是 M 的因子，这就意味着 M % a = 0，M % b = 0，什么意思呢？

     12 = 2 x 6
     12 = 3 x 4
     12 = 4 x 3
     12 = 6 x 2

    在 2 ~ 11 的范围内，12 的因子的确有 2、3、4、6，但是，很显然，我们只需要判断一半，也就是判断 12 % 2 以及 12 % 3 就等于同时判断了后两个因子 12 % 4 和 12 % 6。而这个前后分界线，就是 sqrt(12) = 3，就是说，为了判定 12 是否是素数，我们只需要判定 12 % 2、12 % 3 就足够了，无需再判断后面的 4、5、6、7、8、9、10、11，当然，12 不是素数，本身也无需做完所有的因子判定即可以有结果，但是，如果目标数是一个素数，那就会有意义了，那将使运算效率大幅度提高。
    在本例的代码中，q = sqrt(m) 就是因子分界线，代码逻辑是，如果枚举因子到了 k >= q + 1 都没能找到任何一个因子，那么，无需继续枚举，完全可以断言，m 必然就是一个素数。
        我也提供一个参考代码：  

#include<stdio.h>
int main(void)
{
        int k , m , n                                      ;
        for(m = 100 , n = 0 ; m < 201 ; m ++) {
                for(k = 2 ; k * k < m + 1 && m % k ; k ++) ;
                if(k * k >= m + 1) {                          // 如果关于 k 的循环不是因为 m % k = 0 而结束
                        printf("%3d\t" , m)                ;  // 那么，m 就是一个素数无疑。
                        n ++                               ;
                        if(n % 6 == 0) printf("\n")        ;
                }
        }
}

        编译、运行实况：

D:\[exercise]\C>g++ -o x x.c

D:\[exercise]\C>x
101     103     107     109     113     127
131     137     139     149     151     157
163     167     173     179     181     191
193     197     199
D:\[exercise]\C>

wsb1991abc

你们说的这些我都懂,我不明白的是第二个for循环到11行就结束了,第12行中的K与q+1前面没有写明之间的逻辑关系就拿来比较大小,第二个循环有写明K与Q+1 ,M之间关系,但12行并不能表明有这种关系啊

jackz007

wsb1991abc 发表于 2024-3-5 22:12
你们说的这些我都懂,我不明白的是第二个for循环到11行就结束了,第12行中的K与q+1前面没有写明之间的逻辑关 ...

      for 循环有两种结束途径，一种是自然结束，另一种是 break 结束，那么，二者有什么区别呢，前者是因为循环条件不再成立而结束，后者是在循环条件依然成立的情况下，因为执行了 break 语句而结束。
      下面，让我们来看看这个循环：

          for(k = 2 ; k <= q ; k ++) if(m % k == 0) break ;

      重点聚焦循环的条件，k <= q ，循环结束后，如果 k <= q 依然成立，那么，说明是 break 结束无疑，反之，如果 k <= q 不再成立，说明循环是自然结束无疑。k <= q 与 k >= q + 1 是逻辑互斥关系，就是说，如果 k <= q 不成立，那么，k >= q + 1 就一定会成立，反之亦然。
      所以，第 12 行的功能就是，判断循环结束的方式，并据此判定 m 是否为素数。显然，如果循环自然结束，那么，m 就是素数，否则，m 就不是素数。

wsb1991abc

谢谢大神的回答,毛塞顿开