C语言break和continu的课后作业，求素数第二个for我看不懂是什么意思
请各位老师，兄弟解答一下 判断素数的吧如果它能被其他的书整除，那么就不是素数了 嘉岳呀 发表于 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就是素数
番杰 发表于 2021-11-28 10:24
（1）i 相当于 被除数（就是判断它是不是素数）；
（2）j 相当于 除数（就相当于判断这个j是不是的i的因 ...
j<i/2这一点不是很理解 本帖最后由 jackz007 于 2021-11-28 12:22 编辑
本代码判断素数采用的是排除法，对于每一个 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) 像这样
for(i = 5 ; i < 10000 ; i ++) {
for(j = 2 ; j * j < i + 1 ; j ++) {
此外，除了 2，所有的素数都是奇数，所以，还可以免去对所有偶数的判断，这样，运算效率会提升一倍。
for(count = 0 , i = 3 ; i < 10000 ; i ++) {
flag = 0 ;
if(i % 2) {
for(flag = 1 , j = 3 ; j * j < i + 1 ; j += 2) {
if(! (i % j)) {
flag = 0 ;
break ;
}
}
}
if(flag) count ++ ;
}
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的部分一定也有一个与之对应的因数，反之没的话，就说明他是一个素数
页:
[1]