इस समस्या में, हमें एक संख्या N दी गई है, और हमें उन सभी अद्वितीय अभाज्य गुणनखंडों और उनकी घातों को ढूंढना है जो उस संख्या को विभाजित करते हैं।
विषय को समझने के लिए एक उदाहरण लेते हैं -
इनपुट: 55 आउटपुट: 5 घात 1, 11 घात 1
व्याख्या -
55, 5 और 11 से विभाज्य है।
इस समस्या को हल करने का एक आसान तरीका N के अभाज्य गुणनखंड ढूंढना है। और फिर उस अभाज्य संख्या की घात ढूंढना जो संख्या N को विभाजित करती है और उसे प्रिंट करना।
एल्गोरिदम
कुशल दृष्टिकोण
चरण 1: एक सरणी s[N+1] ढूंढें। s[i] = N को विभाजित करने वाला i का अभाज्य गुणनखंड। चरण 2: i की सभी घातें ढूंढें। अभाज्य = s[N] और घात = 1। चरण 3: जब तक (N > 1) : चरण 3.1: N /= s[N]; चरण 3.2: यदि (अभाज्य == s[N]) : घात++ चरण 4: अभाज्य और घात प्रिंट करें।
उदाहरण
#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
