ในปัญหาที่กำหนด เราจะต้องพิมพ์ตัวหารทั้งหมดของจำนวนเต็มที่กำหนด 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
ในปัญหาที่กำหนด เราสามารถใช้วิธีที่ใช้ในตะแกรง Eratosthenes เพื่อค้นหาตัวหารทั้งหมดของ n
แนวทางในการหาทางออก
ในแนวทางที่กำหนดให้ เราจะใช้แนวคิดที่ใช้ตะแกรงของ Eratosthenes และหาตัวหารของ 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
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เราปฏิบัติตามแนวคิดเดียวกันกับตะแกรงของ Eratosthenes เราพบตัวหารของทุกตัวเลขจนถึง 105 เมื่อเราได้รับคำถาม q เราไม่จำเป็นต้องหาตัวหาร ดังนั้นสิ่งนี้จึงลดความซับซ้อนของเวลาลงอย่างมากเมื่อถูกถามคำถาม q ดังนั้น ความซับซ้อนของเราจึงกลายเป็น O(Q*N) โดยที่ Q คือจำนวนคำถามที่เราจัดการ และ N คือจำนวนตัวหารของ n
บทสรุป
ในบทความนี้ เราแก้ปัญหา:แบบสอบถามเพื่อพิมพ์ตัวหารทั้งหมดของ n ซึ่งเราใช้หลักการของตะแกรงของ Eratosthenes นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
