ปัจจัยเฉพาะของตัวเลขขนาดใหญ่ใน C++ (รองรับถึง 10^18)

ภาพรวมปัญหา

ได้รับจำนวนเต็ม N ≤ 10^18 ต้องพิมพ์ปัจจัยเฉพาะทั้งหมดพร้อมความถี่ของแต่ละตัว

ตัวอย่าง

Input: 100
Output: 2 2    5 2
Explanation: การแยกตัวประกอบเฉพาะของ 100 = 2 × 2 × 5 × 5

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

หาปัจจัยเฉพาะและคำนวณความถี่ โดย:

ตรวจสอบความถี่ของ 2 เป็นตัวหาร แล้วหารตัวเลขด้วย 2 ซ้ำๆ
ตรวจสอบจาก 3 ถึง √n แบบข้ามคี่ (i += 2)
หารและเพิ่มความถี่ของแต่ละจำนวนเฉพาะที่เป็นตัวหาร
หยุดเมื่อตัวเลขกลายเป็น 1
พิมพ์จำนวนเฉพาะทั้งหมดพร้อมความถี่

ตัวอย่างโค้ด C++

#include <iostream>
#include <math.h>
using namespace std;

void factorize(long long n) {
    int count = 0;
    while (!(n % 2)) {
        n /= 2;
        count++;
    }
    if (count)
        cout << 2 << "\t" << count << endl;

    for (long long i = 3; i <= sqrt(n); i += 2) {
        count = 0;
        while (n % i == 0) {
            count++;
            n = n / i;
        }
        if (count)
            cout << i << "\t" << count << endl;
    }
    if (n > 2)
        cout << n << "\t" << 1 << endl;
}

int main() {
    long long N = 21000;
    cout << "The prime factors and their frequencies of the number " << N << " are \n";
    factorize(N);
    return 0;
}

ผลลัพธ์

The prime factors and their frequencies of the number 22000 are
2    3
3    1
5    3
7    1