इस समस्या में, हमें Q संख्या में क्वेरी दी गई हैं, प्रत्येक में एक संख्या N है। हमारा कार्य C++ में क्वेरी को हल करने के लिए एक प्रोग्राम बनाना है कि क्या किसी संख्या में ठीक चार अलग-अलग गुणनखंड हैं या नहीं।
समस्या विवरण
प्रत्येक क्वेरी को हल करने के लिए, हमें यह पता लगाना होगा कि संख्या N में ठीक चार अलग-अलग गुणनखंड हैं या नहीं। यदि हैं तो YES प्रिंट करें, अन्यथा NO।
उदाहरण से समझते हैं
इनपुट: Q = 3, 4, 6, 15
आउटपुट: NO, YES, YES
व्याख्या
क्वेरी 1 के लिए: 4 के गुणनखंड 1, 2, 4 हैं
क्वेरी 2 के लिए: 6 के गुणनखंड 1, 2, 3, 6 हैं
क्वेरी 3 के लिए: 15 के गुणनखंड 1, 3, 5, 15 हैं
समाधान दृष्टिकोण
समस्या का एक सरल समाधान संख्या के सभी गुणनखंड ढूंढकर है। यह 1 से √N तक की सभी संख्याओं को ढूंढकर और काउंटर को 2 से बढ़ाकर किया जाता है। फिर चेक करें कि काउंटर 4 के बराबर है या नहीं और समानता के आधार पर YES या NO प्रिंट करें।
C++ प्रोग्राम उदाहरण (सरल दृष्टिकोण)
#include <iostream>
#include <math.h>
using namespace std;
int solveQuery(int N) {
int factors = 0;
for (int i = 1; i < sqrt(N); i++) {
if (N % i == 0) {
factors += 2;
}
}
if (factors == 4) {
return 1;
}
return 0;
}
int main() {
int Q = 3;
int query[3] = {4, 6, 15};
for (int i = 0; i < Q; i++) {
if (solveQuery(query[i]))
cout << "The number " << query[i] << " has exactly four distinct factors\n";
else
cout << "The number " << query[i] << " does not have exactly four distinct factors\n";
}
}आउटपुट
The number 4 does not have exactly four distinct factors The number 6 has exactly four distinct factors The number 15 has exactly four distinct factors
एक कुशल दृष्टिकोण चार-गुणनखंड संख्याओं के लिए संख्या सिद्धांत की अवधारणाओं का उपयोग करना है। तो, यदि किसी संख्या के चार गुणनखंड हैं तो,
यदि संख्या एक अभाज्य संख्या का घन है। तब इसके चार अलग-अलग गुणनखंड होंगे। उदाहरण, यदि N = (p³), तो गुणनखंड होंगे 1, p, (p²), N।
यदि संख्या दो अलग-अलग अभाज्य संख्याओं का गुणनफल है। तब भी इसके चार अलग-अलग गुणनखंड होंगे। उदाहरण के लिए, यदि N = p1*p2, तो गुणनखंड होंगे 1, p1, p2, N।
C++ प्रोग्राम उदाहरण (कुशल दृष्टिकोण)
#include <bits/stdc++.h>
using namespace std;
int N = 1000;
bool hasFourFactors[1000];
void fourDistinctFactors() {
bool primeNo[N + 1];
memset(primeNo, true, sizeof(primeNo));
for (int i = 2; i <= sqrt(N); i++) {
if (primeNo[i] == true) {
for (int j = i * 2; j <= N; j += i)
primeNo[j] = false;
}
}
vector<int> primes;
for (int i = 2; i <= N; i++)
if (primeNo[i])
primes.push_back(i);
memset(hasFourFactors, false, sizeof(hasFourFactors));
for (int i = 0; i < primes.size(); ++i) {
int p1 = primes[i];
if (1 * (pow(p1, 3)) <= N)
hasFourFactors[p1 * p1 * p1] = true;
for (int j = i + 1; j < primes.size(); ++j) {
int p2 = primes[j];
if (1 * p1 * p2 > N)
break;
hasFourFactors[p1 * p2] = true;
}
}
}
int main() {
int Q = 3;
int query[] = {3, 6, 15};
fourDistinctFactors();
for (int i = 0; i < Q; i++) {
if (hasFourFactors[query[i]])
cout << "The number " << query[i] << " has exactly four distinct factors\n";
else
cout << "The number " << query[i] << " does not have exactly four distinct factors\n";
}
return 0;
}आउटपुट
The number 3 does not have exactly four distinct factors The number 6 has exactly four distinct factors The number 15 has exactly four distinct factors
