3.写一个代码，打印100-200之间的素数：（新思路：试除法）
（判断i是否为素数：用 2到i-1 之间的数字去试除 i，如果能整除则i不是素数）
// 打印100 - 200之间的素数 // 素数 - 质数 // 只能被1和它本身整除的数是质数 // 判断i是否为素数：用 2到i-1 之间的数字去试除 i，如果能整除则i不是素数 // 2到i-1 之间的数字 都不能整除i，则i是素数 #include <stdio.h> int main() { int i = 0; for ( i = 100; i <= 200; i++) //生成100 - 200之间的素数 { // 判断i是否为素数 // 循环产生 2到i-1 int j = 0; int flag = 1; // flag=1 则 i是素数 for ( j = 2; j <= i - 1; j++) // 这个循环产生的就是 2到i-1 的数 // 2 到 i - 1 (用<=) { if (i % j == 0) // 用i模上一个j，看j能不能整除i，有余数则表示不能整除 { flag = 0; // flag=0 则 i不是素数 break; // 有一个j把i整除了，说明i已经不是素数了，所以不用再循环了，break跳出循环 } } if (flag == 1) // 到这里说明i是素数，把它打印出来 { printf("%d ", i); } } return 0; }
（因为偶数除了2都不是素数，且题目范围中没有2，所以可以只生成100 - 200之间的奇数，可以排除一半的数字，效率提升一倍）
// 打印100 - 200之间的素数 // 素数 - 质数 // 只能被1和它本身整除的数是质数 // 判断i是否为素数：用 2到i-1 之间的数字去试除 i，如果能整除则i不是素数 // 2到i-1 之间的数字 都不能整除i，则i是素数 #include <stdio.h> int main() { int i = 0; for ( i = 101; i <= 200; i+=2) //生成100 - 200之间的素数 { // 判断i是否为素数 // 循环产生 2到i-1 int j = 0; int flag = 1; // flag=1 则 i是素数 for ( j = 2; j <= i - 1; j++) // 这个循环产生的就是 2到i-1 的数 // 2 到 i - 1 (用<=) { if (i % j == 0) // 用i模上一个j，看j能不能整除i，有余数则表示不能整除 { flag = 0; // flag=0 则 i不是素数 break; // 有一个j把i整除了，说明i已经不是素数了，所以不用再循环了，break跳出循环 } } if (flag == 1) // 到这里说明i是素数，把它打印出来 { printf("%d ", i); } } return 0; }
（一个数：k, 如果有 k = m * n, 那么一定有m或n小于根号k ，那么可以把之前的 2到i-1 换成 sqrt(i)，即根号i。进一步提高效率）
// 打印100 - 200之间的素数 // 素数 - 质数 // 只能被1和它本身整除的数是质数 // 判断i是否为素数：用 2到i-1 之间的数字去试除 i，如果能整除则i不是素数 // 2到i-1 之间的数字 都不能整除i，则i是素数 #include <stdio.h> #include <math.h> int main() { int i = 0; for ( i = 101; i <= 200; i+=2) //生成100 - 200之间的素数 { // 判断i是否为素数 // 循环产生 2到i-1 int j = 0; int flag = 1; // flag=1 则 i是素数 for ( j = 2; j <= sqrt(i); j++) // 这个循环产生的就是 2到i-1 的数 // 2 到 i - 1 (用<=) //sqrt 是库函数，是开平方的意思 ，需要头文件<math.h> //sqrt(i)就是对i开平方 { if (i % j == 0) // 用i模上一个j，看j能不能整除i，有余数则表示不能整除 { flag = 0; // flag=0 则 i不是素数 break; // 有一个j把i整除了，说明i已经不是素数了，所以不用再循环了，break跳出循环 } } if (flag == 1) // 到这里说明i是素数，把它打印出来 { printf("%d ", i); } } return 0; }
4. 给定两个数，求这两个数的最大公约数：（新思路：辗转相除法）
（思路：用两数中的较小值除以较大值，能整除则较小值就是最大公约数，不能整除则较小值自减1，直到能整除，此时较小值就是最大公约数）
//给定两个数，求这两个数的最大公约数： #include <stdio.h> int main() { int m = 0; int n = 0; scanf("%d %d", &m, &n); // 18 24 //计算 int k = (m > n ? n : m); // 找出较小值 // 使用 条件操作符（三目操作符）条件成立把n赋给k，反之把m赋给k while (1) { if (m % k == 0 && n % k == 0) // 使两个数都能被较小值整除 { break; // 都能被整除则停止 } k--; // 不能整除则较小值自减，再次循环，直到两个数都能被较小值整除 } printf("%d\n", k); return 0; }
（辗转相除法：）
//给定两个数，求这两个数的最大公约数： #include <stdio.h> int main() { int m = 0; int n = 0; scanf("%d %d", &m, &n); // 18 24 //计算 int k = 0; while (k = m % n) // 求余数，当余数为0后停止循环，此时，n为最大公约数 { m = n; // 除数赋给被除数 n = k; // 余数赋给除数 // 赋值后再求余数，直到余数为0 } printf("%d\n", n); return 0; }
