C++ 数论入门：从最大公约数到素数筛法

本文将介绍C++中常用的数论技巧和算法，包括最大公约数、最小公倍数、快速幂算法、质数判定和素数筛法等，并提供代码示例，帮助你快速入门C++数论。\n\n1. 最大公约数（GCD）和最小公倍数（LCM）\n\n最大公约数是两个数的最大公因数，最小公倍数是两个数的最小公倍数。在C++中，可以使用标准库函数__gcd(a, b)来计算最大公约数。例如：\n\ncpp\n#include <iostream>\n#include <algorithm>\nusing namespace std;\n\nint main() {\n int a = 12, b = 18;\n int gcd = __gcd(a, b);\n int lcm = a * b / gcd;\n \n cout << "GCD: " << gcd << endl;\n cout << "LCM: " << lcm << endl;\n \n return 0;\n}\n\n\n输出结果为：\n\n\nGCD: 6\nLCM: 36\n\n\n2. 快速幂算法\n\n快速幂算法用于计算一个数的幂，可以在较短的时间内得到结果。在C++中，可以使用循环或递归来实现快速幂算法。例如，使用循环实现：\n\ncpp\n#include <iostream>\nusing namespace std;\n\nint fastPower(int x, int n) {\n int result = 1;\n \n while (n > 0) {\n if (n % 2 == 1) {\n result *= x;\n }\n \n x *= x;\n n /= 2;\n }\n \n return result;\n}\n\nint main() {\n int x = 2, n = 5;\n int result = fastPower(x, n);\n \n cout << x << " raised to the power of " << n << " is: " << result << endl;\n \n return 0;\n}\n\n\n输出结果为：\n\n\n2 raised to the power of 5 is: 32\n\n\n3. 质数判定\n\n质数是只能被1和自身整除的数。在C++中，可以使用以下代码来判断一个数是否为质数：\n\ncpp\n#include <iostream>\nusing namespace std;\n\nbool isPrime(int n) {\n if (n <= 1) {\n return false;\n }\n \n for (int i = 2; i * i <= n; i++) {\n if (n % i == 0) {\n return false;\n }\n }\n \n return true;\n}\n\nint main() {\n int n = 17;\n bool result = isPrime(n);\n \n if (result) {\n cout << n << " is a prime number" << endl;\n } else {\n cout << n << " is not a prime number" << endl;\n }\n \n return 0;\n}\n\n\n输出结果为：\n\n\n17 is a prime number\n\n\n4. 素数筛法\n\n素数筛法是一种高效的寻找质数的算法。它的基本思想是从2开始，将其倍数标记为非质数，然后继续寻找下一个未被标记的数，重复这个过程，直到找到所有的质数。以下是使用素数筛法找出小于等于n的所有质数的代码示例：\n\ncpp\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nvector<int> sieveOfEratosthenes(int n) {\n vector<bool> isPrime(n + 1, true);\n vector<int> primes;\n \n for (int i = 2; i * i <= n; i++) {\n if (isPrime[i]) {\n for (int j = i * i; j <= n; j += i) {\n isPrime[j] = false;\n }\n }\n }\n \n for (int i = 2; i <= n; i++) {\n if (isPrime[i]) {\n primes.push_back(i);\n }\n }\n \n return primes;\n}\n\nint main() {\n int n = 20;\n vector<int> primes = sieveOfEratosthenes(n);\n \n cout << "Prime numbers less than or equal to " << n << ": ";\n for (int prime : primes) {\n cout << prime << " ";\n }\n cout << endl;\n \n return 0;\n}\n\n\n输出结果为：\n\n\nPrime numbers less than or equal to 20: 2 3 5 7 11 13 17 19\n\n\n以上是C++数论的一些基础知识和技巧。希望这篇博客能够帮助你入门C++数论，并在实际问题中有所应用。