모든 소인수와 그 힘을 C++로 인쇄

이 문제에서 우리는 숫자 N이 주어지고, 우리는 그 숫자를 나누는 모든 고유한 소인수와 그 거듭제곱을 찾아야 합니다.

주제를 이해하기 위해 예를 들어 보겠습니다 -

Input: 55
Output:
5 power 1
11 power 1

설명 -

55는 5와 11로 나누어집니다.

이 문제를 풀기 위한 쉬운 방법은 N의 소인수를 구하는 것입니다. 그런 다음 숫자 N을 나누는 소수의 거듭제곱을 구하여 인쇄하십시오.

알고리즘

효율적인 접근 방식

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.

예시

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

출력

주요 요인은 이고 그 힘은 −

Factor Power
5 1
11 1