我一直在努力提高速度，但在網上沒有找到任何有用的東西。我也在使用 boost::multiprecision 1024 位整數。找到如此大數的所有倍數的最快方法是什么？
我努力了：
- 從 1 回圈到數字的平方根
- 如果數字是奇數，則增加 2
- 保持我能做的一切都在回圈之外
- 在發布模式下編譯（vs2019）
到目前為止，這是我的代碼。
#include <iostream>
#include <time.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;
void multiples()
{
__int64 startthing, endthing;
__int64 freq = _Query_perf_frequency();
int1024_t divisor = 0, thing = 0;
while (1)
{
//displayer.join();
cout << "\nEnter a number\n";
cin >> thing;
if (thing == 0 && !cin.fail())
break;
cout << endl;
while (cin.fail())
{
cout << "I said integer you rule breaker\n";
// get rid of failure state
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cin >> thing;
}
int1024_t limit = sqrt(thing);
int1024_t step = (thing & 1 ? 2 : 1); // odd number = odd factors
startthing = _Query_perf_counter(); // start timer
for (int1024_t i = 1; i <= limit; i = step)
{
if ((thing % i) == 0)
{
divisor = thing / i;
cout << i << ", " << divisor << "\n";
}
}
endthing = _Query_perf_counter();
cout << "\nThat took " << (endthing - startthing) / (double)freq << " seconds.\n";
}
}
uj5u.com熱心網友回復：
這里最好的方法可能是計算數字的質因數分解，然后列印出這些質因數的所有可能組合的乘積。
這是一個使用 uint64_t 而不是多精度的沒有太多優化的實作，它在我機器上的輸入 10,000,000,000,000,000 的 305 毫秒內完成。
請注意，對于大量不同的質因數，性能會明顯變差。（最小的 14 個素數的乘積為 12132 毫秒）。這是由于需要計算/列印的組合更多。
#include <chrono>
#include <iostream>
#include <utility>
#include <vector>
using PrimeFactors = std::vector<std::pair<uint64_t, uint64_t>>;
std::vector<std::pair<uint64_t, uint64_t>> FindFactors(uint64_t n)
{
PrimeFactors primeFactors;
uint64_t square = static_cast<uint64_t>(std::sqrt(n));
for (uint64_t i = 2; i <= square && i <= n; i)
{
bool isPrime = true;
for (auto [prime, exponent] : primeFactors)
{
if (prime * prime > i)
{
break;
}
if (i % prime == 0u)
{
isPrime = false;
break;
}
}
if (isPrime)
{
uint64_t count = 0;
while (n % i == 0)
{
count;
n /= i;
}
primeFactors.emplace_back(i, count);
if (count != 0)
{
square = static_cast<uint64_t>(std::sqrt(n));
}
}
}
if (n != 1)
{
primeFactors.emplace_back(n, 1);
}
return primeFactors;
}
void PrintFactors(uint64_t factor, PrimeFactors::const_iterator pos, PrimeFactors::const_iterator const end)
{
while (pos != end)
{
while (pos != end && pos->second == 0)
{
pos;
}
auto newFactor = factor;
for (auto count = pos->second; count != 0; --count)
{
newFactor *= pos->first;
std::cout << newFactor << '\n';
PrintFactors(newFactor, pos 1, end);
}
pos;
}
}
int main()
{
using Clock = std::chrono::steady_clock;
uint64_t const input = 10'000'000'000'000'000ull;
//uint64_t const input = 2ull * 3ull * 5ull * 7ull *11ull * 13ull *17ull * 19ull * 23ull * 29ull *31ull*37ull * 41ull*43ull;
auto start = Clock::now();
auto factors = FindFactors(input);
// print
std::cout << 1 << '\n';
PrintFactors(1, factors.begin(), factors.end());
auto end = Clock::now();
std::cout << "took " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms\n";
}
uj5u.com熱心網友回復：
潛在的錯誤
int1024_t limit = sqrt(thing);有不精確的風險，因為它使用精度低于 的 FP 數學int1024_t。
一個好的編譯器會在附近計算，a % b并且僅a / b花費大約相同的時間成本a % b。
所以代替i <= limit.
// for (int1024_t i = 1; i <= limit; i = step)
for (int1024_t i = 1; i <= thing/i; i = step)
{
if ((thing % i) == 0)
...
因素
一種更復雜的方法，但加快速度是減少thing找到的每個因素。使用 72，形成集合 1,2,2,2,3,3 來報告因子。這很快避免了合數的多次迭代——對素數沒有任何作用。
最好有一個質數串列 - 初始固定 - 或隨時計算，以辨別下一個劃分候選者。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/386259.html
上一篇：如何過濾繼承的物件？