此题数据范围为1 <n< 10的18次方请给出性能更高的c++详细代码
时间: 2024-10-02 20:02:24 浏览: 26
a的n次方 C++
针对大规模数据范围 \(1 < n < 10^{18}\),我们可以通过优化质因数分解过程来提高代码的性能。一个常见的优化策略是使用埃拉托斯特尼筛法(Sieve of Eratosthenes)预先生成所有小素数,然后在找到每个数的质因子时直接从已知素数列表中获取。以下是优化后的代码:
```cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> sieveOfEratosthenes(int n) {
vector<bool> isPrime(n+1, true);
vector<int> primes;
for (int p=2; p*p<=n; ++p) {
if (isPrime[p]) {
primes.push_back(p);
for (int i=p*p; i<=n; i += p)
isPrime[i] = false;
}
}
// 将大于 sqrt(n) 的素数添加至 primes 后面
for (int p = n; p > 1 && primes.back() * primes.back() <= n; p--)
if (isPrime[p])
primes.push_back(p);
return primes;
}
int countMutuallyCoprimeGroups(int n) {
vector<int> primes = sieveOfEratosthenes(sqrtl(n));
int product = 1;
for (const auto &prime : primes) {
int exponent = 0;
while (product <= n && product % prime == 0) {
product *= prime;
++exponent;
}
// 每增加一个质因子,堆的数量会乘以当前质因子减一,然后加一次之前产生的堆数
int newPiles = primes.size() * exponent;
int oldPiles = product > n ? primes.size() - exponent : 1;
minHeapCount = min(minHeapCount, newPiles + oldPiles - 1);
}
return minHeapCount;
}
int main() {
long long n;
cout << "Enter the value of n: ";
cin >> n;
int minHeapCount = countMutuallyCoprimeGroups(n);
cout << "Minimum number of piles to make all numbers mutually co-prime up to " << n << " is: " << minHeapCount << endl;
return 0;
}
```
在这个版本中,我们用埃拉托斯特尼筛法生成了小于等于 `sqrt(n)` 的所有素数,然后遍历这些素数并计算它们能分别构成的堆数。这比每次循环都要检查所有小于 `n` 的数更高效。
阅读全文