Trong bài toán đã cho, chúng ta bắt buộc phải in ra tất cả các ước của một số nguyên n cho trước.
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
Trong bài toán đã cho, chúng ta có thể áp dụng phương pháp được sử dụng trong sàng Eratosthenes để tìm tất cả các ước của n.
Phương pháp tiếp cận để tìm ra giải pháp
Trong cách tiếp cận đã cho, chúng tôi sẽ áp dụng khái niệm dựa trên sàng của Eratosthenes và tìm các ước của n.
Ví dụ
#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;
} Đầu ra
1 2 3 6 1 2 3 5 6 10 15 30
Giải thích về đoạn mã trên
Trong cách tiếp cận này, chúng tôi tuân theo khái niệm tương tự như sàng của Eratosthenes. Chúng tôi tìm ước số của mọi số cho đến 105. Khi chúng tôi được cung cấp q truy vấn, chúng tôi không cần phải tìm ước số, vì vậy điều này làm giảm đáng kể độ phức tạp về thời gian của chúng tôi khi được hỏi q truy vấn. Do đó, độ phức tạp của chúng ta trở thành O (Q * N), trong đó Q là số truy vấn chúng ta giải quyết và N là số ước của n.
Kết luận
Trong bài này, chúng tôi giải quyết một vấn đề:Truy vấn để in ra tất cả các ước của n trong đó chúng tôi áp dụng nguyên lý sàng của Eratosthenes. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.