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

平方根よりも大きいものは n の因数にならないため、n ではなく n の平方根まで反復できます。編集：ComicSansMsの回答を読んで、私の編集よりも優れていました

于 2014-07-31T14:33:25.520 に答える