C++ を使用して n のすべての因数を出力するクエリ

指定された問題では、指定された整数 n のすべての約数を出力する必要があります。

Input: 15
Output: 1 3 5 15
Explanation
Divisors of 15 are: 1,3, 5, 15

Input: 30
Output: 1 2 3 5 15 30

与えられた問題では、エラトステネスのふるいで使用される方法を適用して、n のすべての約数を見つけることができます。

解を見つける方法

指定された方法では、エラトステネスのふるいの概念を適用し、n の約数を求めます。

例

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

vector<int> divisors[100001]; // our vector containing number with all of its divisors
void findsieve(int max) { // filling data in vector divisors till 10e5
   for(int i = 1; i <= max; i++) {
      for(int j = i; j <= max; j += i)
         divisors[j].push_back(i);
   }
}
void __print(int n){ // the function to print divisors
   for(auto x : divisors[n])
      cout << x << " ";
   cout << "\n";
}

int main() {
   findsieve(100000); // we hardcode the sieve and divisors till 10e5
   int n = 6; // the given n
   __print(n);
   n = 30; // new n
   __print(n);
   return 0;
}

出力

1 2 3 6
1 2 3 5 6 10 15 30

上記のコードの説明

このメソッドでは、エラトステネスの篩と同じ概念に従います。 105 までのすべての数の約数を求めます。 q 個のクエリを受信するときに除数を見つける必要がないため、q 個のクエリを実行する際の時間の複雑さが大幅に軽減されます。したがって、複雑さは O(Q*N) になります。ここで、Q は処理するクエリの数、N は n の約数の数です。

結論

この記事では、エラトステネスのふるいの原理を適用して、n のすべての約数を出力するクエリの問題を解決しました。また、この問題を解決するための C プログラムと、この問題を解決するための完全な方法 (通常) も学習しました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して n のすべての因数を出力するクエリの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。