คิวรีเพื่อพิมพ์ตัวหารทั้งหมดของ n โดยใช้ C++

ในปัญหาที่กำหนด เราต้องพิมพ์ตัวหารทั้งหมดของจำนวนเต็ม n ที่กำหนด

Input: 15
Output: 1 3 5 15
คำอธิบาย: ตัวหารของ 15 คือ: 1, 3, 5, 15

Input: 30
Output: 1 2 3 5 15 30

ในปัญหาที่กำหนด เราสามารถนำวิธีการที่ใช้ใน Sieve of Eratosthenes มาใช้เพื่อหาตัวหารทั้งหมดของ n

วิธีการแก้ปัญหา

ในวิธีการที่กำหนด เราจะนำแนวคิดที่ Sieve of Eratosthenes ใช้มาใช้ และหาตัวหารของ n

ตัวอย่าง

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

vector divisors[100001]; // เวกเตอร์เก็บตัวเลขพร้อมตัวหารทั้งหมด

void findsieve(int max) {
    // เติมข้อมูลใน divisors จนถึง 10^5
    for(int i = 1; i <= max; i++) {
        for(int j = i; j <= max; j += i)
            divisors[j].push_back(i);
    }
}

void __print(int n){
    // ฟังก์ชันพิมพ์ตัวหาร
    for(auto x : divisors[n])
        cout << x << " ";
    cout << "\n";
}

int main() {
    findsieve(100000); // เรา hardcode sieve และตัวหารจนถึง 10^5
    int n = 6; // n ที่กำหนด
    __print(n);
    n = 30; // n ใหม่
    __print(n);
    return 0;
}

ผลลัพธ์

1 2 3 6
1 2 3 5 6 10 15 30

คำอธิบายโค้ด

ในวิธีนี้ เราทำตามแนวคิดเดียวกับ Sieve of Eratosthenes เราหาตัวหารของทุกตัวเลขจนถึง 10^5 เมื่อเราได้รับ q คิวรี เราไม่ต้องหาตัวหารอีก ดังนั้นลดความซับซ้อนด้านเวลาลงอย่างมากเมื่อถูกถาม q คิวรี ดังนั้นความซับซ้อนของเราจะกลายเป็น O(Q×N) โดยที่ Q คือจำนวนคิวรีที่เราจัดการ และ N คือจำนวนตัวหารของ n

สรุป

ในบทความนี้ เราแก้ปัญหา: คิวรีเพื่อพิมพ์ตัวหารทั้งหมดของ n โดยเรานำหลักการของ Sieve of Eratosthenes มาใช้ เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดา) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์