Các thừa số nguyên tố của một số lớn trong C ++

Trong bài toán này, chúng ta được cung cấp một số nguyên N <=10 ^ 18. Nhiệm vụ của chúng ta là in ra tất cả các thừa số nguyên tố của một số cùng với tần suất xuất hiện.

Hãy lấy một ví dụ để hiểu vấn đề,

Input: 100
Output: 2 2
   5 2
Explanation: prime factorization of 100 = 2 * 2 * 5 * 5.

Để giải quyết vấn đề này, chúng ta sẽ phải tìm các thừa số nguyên tố của một số và sau đó tính tần số của chúng.

Đối với điều này, chúng ta sẽ tìm kiểm tra tần số của 2 như một thừa số và chia số cho 2. Sau đó kiểm tra từ 3 đến căn bậc hai n. chia và tăng tần số của mỗi số nguyên tố là một thừa số của số đó. Và dừng lại nếu số trở thành 1. Sau đó in tất cả các số nguyên tố có tần số ở đó.

Đoạn mã dưới đây cho thấy việc triển khai giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

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