In tất cả các thừa số nguyên tố và lũy thừa của chúng trong C++

Trong bài toán này, cho một số N, ta phải tìm tất cả các thừa số nguyên tố duy nhất và lũy thừa của chúng chia hết cho số đó.

Ví dụ để hiểu rõ:

Input: 55 Output: 5 power 1 11 power 1

Giải thích: 55 chia hết cho 5 và 11.

Để giải bài toán, cách tiếp cận dễ dàng là tìm các thừa số nguyên tố của N. Sau đó tìm lũy thừa của số nguyên tố đó chia hết N và in ra.

Thuật toán hiệu quả

Bước 1: Tìm mảng s[N+1]. s[i] = thừa số nguyên tố của i chia N.
Bước 2: Tìm tất cả các lũy thừa của i. prime = s[N] và pow = 1.
Bước 3: While (N > 1):
    Bước 3.1: N /= s[N];
    Bước 3.2: if (prime == s[N]): pow++
Bước 4: In prime và pow.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;
void primes(int N, int s[]){
    vector<bool> prime(N + 1, false);
    for (int i = 2; i <= N; i += 2)
        s[i] = 2;
    for (int i = 3; i <= N; i += 2){
        if (prime[i] == false){
            s[i] = i;
            for (int j = i; j * i <= N; j += 2){
                if (prime[i * j] == false){
                    prime[i * j] = true;
                    s[i * j] = i;
                }
            }
        }
    }
}
void generatePrimeFactors(int N) {
    int s[N + 1];
    primes(N, s);
    cout << "Factor\tPower" << endl;
    int prime = s[N];
    int power = 1;
    while (N > 1){
        N /= s[N];
        if (prime == s[N]){
            power++;
            continue;
        }
        cout << prime << "\t" << power << endl;
        prime = s[N];
        power = 1;
    }
}
int main() {
    int N = 55;
    cout << "Các thừa số nguyên tố và lũy thừa của chúng:\n";
    generatePrimeFactors(N);
    return 0;
}

Kết quả

Các thừa số nguyên tố và lũy thừa của chúng là:

Factor Power
5 1
11 1