Cho N và k. Nhiệm vụ: tìm ước số thứ k nhỏ nhất của N.
Ví dụ minh họa
Input: N = 15, k = 3 Output: 5
Ước của 15: 1, 3, 5, 15. Thứ 3 là 5.
Phương pháp 1: Thu thập và sắp xếp ước số O(√n log n)
Duyệt i từ 1 đến √n, nếu chia hết thêm i và n/i vào mảng, sắp xếp, lấy phần tử k-1.
Phương pháp 2: Hai mảng đã sắp xếp O(√n)
Mảng 1: các ước i tăng dần. Mảng 2: các ước n/i giảm dần. Kết hợp để lấy phần tử k mà không cần sort.
Ví dụ chương trình (Phương pháp 2)
#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
vector<int> factors1, factors2;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
factors1.push_back(i);
if (i != n / i) factors2.push_back(n / i);
}
}
if (k > factors1.size() + factors2.size()) {
cout << "Không tồn tại";
} else if (k <= factors1.size()) {
cout << factors1[k - 1];
} else {
cout << factors2[factors2.size() - (k - factors1.size())];
}
}
int main(){
int N = 16, k = 3;
cout << k << "-th ước nhỏ nhất của " << N << " là ";
findFactorK(N, k);
return 0;
}
Kết quả
3-th ước nhỏ nhất của 16 là 4