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, chúng ta được cho một số N và chúng 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 sẽ chia số.

Hãy lấy một ví dụ để hiểu chủ đề -

Input: 55
Output:
5 power 1
11 power 1

Giải thích -

55 chia hết cho 5 và 11.

Để giải quyết vấn đề này, một cách dễ dàng để giải quyết vấn đề là tìm các thừa số nguyên tố của N. Và sau đó tìm lũy thừa của số nguyên tố chia hết số N và in ra.

Thuật toán

Phương pháp tiếp cận hiệu quả

Step 1: Find an array s[N+1].
s[i] = prime factor of i dividing N.
Step 2: Find all powers of i. prime = s[N] and pow = 1.
Step 3: While (N > 1) :
   Step 3.1: N /= s[N];
   Step 3.2: if(prime = s[N]) : pow++
Step 4: print prime and pow.

Ví dụ

#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<<"The prime factors are and their powers are :\n";
   generatePrimeFactors(N);
   return 0;
}

Đầu ra

Các yếu tố chính là và sức mạnh của chúng -

Factor Power
5 1
11 1