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 ++プログラムと、この問題を解決するための完全なアプローチ（Normal）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。