Pertanyaan untuk mencetak semua faktor n menggunakan C++

Dalam masalah yang diberikan, kita perlu mencetak semua pembahagi bagi integer n yang diberikan.

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

Dalam masalah yang diberikan, kita boleh menggunakan kaedah yang digunakan dalam Ayak Eratosthenes untuk mencari semua pembahagi n.

Kaedah untuk mencari penyelesaian

Dalam kaedah yang diberikan, kita akan menggunakan konsep Ayak Eratosthenes dan mencari pembahagi n.

Contoh

#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

Penjelasan kod di atas

Dalam kaedah ini kita mengikut konsep yang sama seperti Sieve of Eratosthenes. Kami mencari pembahagi setiap nombor hingga 105. Kami tidak perlu mencari pembahagi apabila kami menerima pertanyaan q, jadi ini sangat mengurangkan kerumitan masa kami apabila bertanya pertanyaan q. Oleh itu, kerumitan kita menjadi O(Q*N), di mana Q ialah bilangan pertanyaan yang kita proses dan N ialah bilangan pembahagi n.

Kesimpulan

Dalam artikel ini kami menyelesaikan masalah pencetakan pertanyaan semua pembahagi n, di mana kami menggunakan prinsip Ayak Eratosthenes. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan kaedah lengkap untuk menyelesaikan masalah ini (Normal). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Pertanyaan untuk mencetak semua faktor n menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!