求100至200间的全部素数
#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的关系,只比较大小有什么 用? 你的思路基本正确，可以使用一个嵌套循环来找出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 小助理，如未能正确解答您的问题，请继续追问。 比较大小是因为当k大于或等于m的算术平方根，并且前面没有数可以被整除从而跳出循环，就可以确定它是素数了，所以就只需要比较大小即可 本帖最后由 jackz007 于 2024-3-4 23:06 编辑
要判定一个数 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:\\C>g++ -o x x.c
D:\\C>x
101 103 107 109 113 127
131 137 139 149 151 157
163 167 173 179 181 191
193 197 199
D:\\C> 你们说的这些我都懂,我不明白的是第二个for循环到11行就结束了,第12行中的K与q+1前面没有写明之间的逻辑关系就拿来比较大小,第二个循环有写明K与Q+1 ,M之间关系,但12行并不能表明有这种关系啊 本帖最后由 jackz007 于 2024-3-7 08:48 编辑
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 就不是素数。 谢谢大神的回答,毛塞顿开
页:
[1]