什么叫质数,如何理解这段代码#include <iostream> using namespace std; // 求最大公约数 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { int m, n; cin >> m >> n; if (gcd(m, n) == 1) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }
时间: 2024-04-01 09:31:04 浏览: 16
质数,也叫素数,是指只能被 1 和它本身整除的正整数。比如 2、3、5、7、11 等都是质数,而 4、6、8、9 等都不是质数。
这段代码首先定义了一个 `gcd` 函数,用于求两个数的最大公约数。其中,递归的方式实现了辗转相除法。接下来,在 `main` 函数中,读入两个正整数 `m` 和 `n`,然后调用 `gcd` 函数求它们的最大公约数。如果最大公约数等于 1,那么它们就是互质的,输出 "Yes";否则输出 "No"。这个程序可以用来判断两个数是否互质。
相关问题
对此代码进行优化#include <iostream> #include <vector> using namespace std; // 求最大公约数 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // 获取所有分母小于等于 n 的最简分数 vector<pair<int, int>> getFractions(int n) { vector<pair<int, int>> res; // 存储最简分数的数组 for (int i = 2; i <= n; i++) { // 枚举分母 i for (int j = 1; j < i; j++) { // 枚举分子 j if (gcd(i, j) == 1) { // 判断是否为最简分数 res.push_back({j, i}); // 存储最简分数 } } } return res; } int main() { int n; while (cin >> n && n != 0 && n<=100) { // 循环读入每个正整数 vector<pair<int, int>> res = getFractions(n); // 求解最简分数 for (auto p : res) { // 遍历最简分数数组 cout << p.first << "/" << p.second << " "; // 输出最简分数 } cout << endl; } return 0; }
对于这段代码,可以进行如下优化:
1. 在判断是否为最简分数时,可以将判断i和j是否互质的操作提取出来,使用一个单独的函数进行判断,可以减少gcd函数的调用次数。
2. 对于每个正整数n,可以使用一个数组存储小于等于n的所有质数,然后在判断i和j是否互质时,只需要判断j是否为n以内的质数即可,因为i已经是n以内的数,只有当j为质数时才有可能是最简分数,因此不需要枚举所有的j。
3. 在输出最简分数时,可以使用字符串流stringstream,将分子和分母转换成字符串后拼接输出,可以避免使用多个输出操作符<<。
优化后的代码如下所示:
```
#include <iostream>
#include <vector>
#include <sstream>
#include <cmath>
using namespace std;
// 判断两个数是否互质
bool isCoprime(int a, int b) {
return gcd(a, b) == 1;
}
// 获取所有分母小于等于 n 的最简分数
vector<pair<int, int>> getFractions(int n) {
vector<pair<int, int>> res; // 存储最简分数的数组
vector<int> primes; // 存储小于等于n的所有质数
primes.push_back(2); // 2是第一个质数
for (int i = 3; i <= n; i++) {
bool isPrime = true;
for (auto p : primes) {
if (p > sqrt(i)) {
break;
}
if (i % p == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
primes.push_back(i);
}
}
for (int i = 2; i <= n; i++) { // 枚举分母 i
for (auto p : primes) {
if (p > i) {
break;
}
if (i % p == 0) {
goto next_i; // i不是质数,跳过
}
}
for (int j = 1; j < i; j++) { // 枚举分子 j
if (j > n || !isCoprime(i, j)) {
continue;
}
res.push_back({j, i}); // 存储最简分数
}
next_i:
continue;
}
return res;
}
int main() {
int n;
while (cin >> n && n != 0 && n <= 100) { // 循环读入每个正整数
vector<pair<int, int>> res = getFractions(n); // 求解最简分数
for (auto p : res) { // 遍历最简分数数组
stringstream ss;
ss << p.first << "/" << p.second << " ";
cout << ss.str(); // 输出最简分数
}
cout << endl;
}
return 0;
}
```
经过优化后,代码的可读性和执行效率都得到了提高。
写一个c++代码,解决下列问题:从键盘输入两个 2 位正整数,判断每个数是否为素数,求每个数的因子之和,以及它们 的最大公约数、最小公倍数。
下面是一个解决该问题的C++代码,其中包含了求素数、因子之和、最大公约数和最小公倍数的函数。
```c++
#include <iostream>
using namespace std;
// 判断素数函数
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
// 计算因子之和函数
int sumFactors(int n) {
int sum = 1;
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
sum += i;
}
}
return sum;
}
// 计算最大公约数函数
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 计算最小公倍数函数
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main() {
int a, b;
cout << "请输入两个2位正整数:";
cin >> a >> b;
// 判断并输出a是否为素数
if (isPrime(a)) {
cout << a << "是素数" << endl;
} else {
cout << a << "不是素数" << endl;
}
// 计算并输出a的因子之和
cout << a << "的因子之和为:" << sumFactors(a) << endl;
// 判断并输出b是否为素数
if (isPrime(b)) {
cout << b << "是素数" << endl;
} else {
cout << b << "不是素数" << endl;
}
// 计算并输出b的因子之和
cout << b << "的因子之和为:" << sumFactors(b) << endl;
// 计算并输出a和b的最大公约数
cout << a << "和" << b << "的最大公约数为:" << gcd(a, b) << endl;
// 计算并输出a和b的最小公倍数
cout << a << "和" << b << "的最小公倍数为:" << lcm(a, b) << endl;
return 0;
}
```
注意,该代码只能判断和计算2位正整数的素数、因子之和、最大公约数和最小公倍数。如果输入的数不符合条件,程序可能会出现错误。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)