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의 약수를 구해보겠습니다.

Example

#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;
}

Output

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!