0

我正在尝试这个，但是在输入>10000 时，这个循环 ID 需要更多时间。

有什么方法可以优化这个时间复杂度小于 N 或 (logn) 的方法吗？

#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
    int n = 10001;

    for (int i = 1; i < n; i++) {
        if (n % i == 0) {
            cout << i;
        }
    }
    return 0;
}
4

4 回答 4

2

除了dmh2000 的回答：您可以在检查中利用冗余。例如，如果一个数不能被它整除，n它也不能被 的任何倍数整除n。例如，一个不能被 2 整除的数也不能被 4、6 或 8 整除。

这种技术被称为筛分。

于 2014-07-31T14:37:50.463 回答
1

First step is to find all the prime factors, with their multiplicity. Then you can generate the factors easily.

Finding the prime factors is quite fast on average for numbers up to about 100000000, if you do it sensibly. If you find a factor, you can divide it out of n, which reduces the time enormously in the general case. Also you only need to check odd factors up to sqrt(n), apart from 2:

// I assume n is non-zero
while (!(n & 1)) {
    cout << "2" << endl;
    n /= 2;
}
for (unsigned int factor = 3; factor * factor <= n; factor += 2) {
    while (n % factor == 0) {
        cout << factor << endl;
        n /= factor;
    }
if (n != 1)
    cout << n << endl;
}
于 2014-07-31T15:04:13.847 回答
1

您可以只迭代 n 的平方根而不是 n，因为任何大于平方根的东西都不能是 n 的因数。编辑：阅读 ComicSansMs 的答案比我的编辑好

于 2014-07-31T14:33:25.520 回答
0

如果您需要多次执行此操作，有一个很好的解决方案。我只举一个例子，实施将是你的事。

假设您需要分解两个数字，例如 580 和 72。

一开始你把它分解成素数

580 = 2 x 2 x 5 x 29
72 = 2 x 2 x 2 x 3 x 3

使用缓存可以大大提高分解为素数的速度。你应该有std::set<int>which 包含所有已知的素数，所以在分解后580它包含2, 5, 29. 这意味着分解72你只需要确定它3是素数。

在您拥有所有主要因素后，您需要将它们以所有组合相乘以获得非主要因素。

正如我所提到的，这个解决方案只有在你需要分解许多数字的情况下才真正好用，但如果你只需要分解一次它就不错了，筛分会更好。

于 2014-07-31T15:05:32.030 回答