N को 0 तक कम करने के लिए आवश्यक संक्रियाओं की गणना (सबसे छोटे अभाज्य भाजक घटाना) - C++

समस्या विवरण

हमें एक धनात्मक पूर्णांक N दिया गया है। लक्ष्य N को 0 तक कम करने के लिए आवश्यक संक्रियाओं की संख्या ज्ञात करना है। संक्रिया: N = N - P जहाँ P वर्तमान N का सबसे छोटा अभाज्य भाजक है।

उदाहरण

इनपुट: N = 17

आउटपुट: 1

व्याख्या: 17 का सबसे छोटा अभाज्य भाजक 17 है। 17-17=0, एक संक्रिया।

इनपुट: N = 20

आउटपुट: 10

व्याख्या: सबसे छोटा अभाज्य भाजक 2 है। 2 को बार-बार घटाने पर: 20→18→16→...→2→0 (10 बार)।

दृष्टिकोण

सभी सम संख्याओं के लिए सबसे छोटा अभाज्य भाजक 2 होता है। विषम संख्याओं के लिए, सबसे छोटा अभाज्य भाजक विषम होता है; घटाने के बाद संख्या सम हो जाती है, फिर 2 बार-बार घटाया जाता है।

i=2 से शुरू करके सबसे छोटा भाजक खोजें। यदि i*i > N तो i = N (N अभाज्य है)। कुल संक्रियाएँ = 1 + (N - i)/2।

एल्गोरिदम

1. प्रारंभिक i = 2
2. while (i*i < N && N%i != 0) i++
3. यदि i*i > N तो i = N
4. count = 1 + (N - i)/2
5. count लौटाएँ

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

int N_to_Zero(int N) {
    int i = 2;
    while ((i * i) < N && (N % i)) i++;
    if ((i * i) > N) i = N;
    return 1 + (N - i) / 2;
}

int main() {
    int N = 10;
    cout << "Count: " << N_to_Zero(N);
    return 0;
}

आउटपुट

Count: 5