Tính toán thừa số nguyên tố bằng cách sử dụng Sieve O (log n) cho nhiều truy vấn trong C ++

Trong bài toán này, chúng ta cần tạo một chương trình để tính toán Nguyên tố thừa số bằng cách sử dụng Sàng O (log n) cho nhiều truy vấn.

Vì phương pháp chung cần thời gian O (sqrt (n)), điều này sẽ làm tăng thời gian cần thiết từ nhiều truy vấn.

Trước tiên hãy tóm tắt lại,

Phân tích thừa số nguyên tố của một số CHỈ bao gồm các thừa số nguyên tố, không phải bất kỳ tích nào của các thừa số nguyên tố đó.

Rây Eratosthenes là một thuật toán để tạo ra tất cả các số nguyên tố trong phạm vi đã cho.

Phương pháp tiếp cận giải pháp

Giải pháp cho vấn đề được tìm thấy bằng cách tìm thừa số nhỏ nhất chia số đó, lưu nó dưới dạng thừa số và cập nhật số bằng cách chia nó cho thừa số. Quá trình này được thực hiện đệ quy cho đến khi số trở thành 1 sau khi chia, có nghĩa là không có yếu tố nào khác.

Tính toán được thực hiện bằng cách sử dụng sàng eratosthenes điều này làm giảm thời gian phức tạp trong việc tìm thừa số nguyên tố nhỏ nhất.

Chương trình minh họa hoạt động của giải pháp của chúng tôi

Ví dụ

#include <iostream>
using namespace std;
int primes[100001];

void sieveOfEratosthenes(int N) {
   
   N+=2;
   primes[1] = 1;
   for (int i=2; i<N; i++)
      primes[i] = i;
   for (int i=4; i<N; i+=2)
      primes[i] = 2;
   for (int i=3; i*i<N; i++) {
      if (primes[i] == i) {
         for (int j=i*i; j<N; j+=i)
            if (primes[j]==j)
               primes[j] = i;
      }
   }
}
void findPrimeFactors(int num) {
   
   sieveOfEratosthenes(num);
   int factor;
   while (num != 1) {
      factor = primes[num];
      cout<<factor<<" ";
      num /= factor;
   }
}

int main() {
   int N = 45214;
   cout<<"Prime factorization of the number "<<N<<" using sieve is ";
   findPrimeFactors(N);
   return 0;
}

Đầu ra

Prime factorization of the number 45214 using sieve is 2 13 37 47