पायथन में एन को 1 तक कम करने के लिए अधिकतम संचालन खोजें

मान लीजिए कि हमारे पास दो संख्याएँ P और Q हैं और वे एक संख्या N =(P!/Q!) बनाते हैं। हमें यथासंभव अधिक से अधिक संक्रियाएँ निष्पादित करके N को घटाकर 1 करना होगा। प्रत्येक ऑपरेशन में, कोई N को N/X से बदल सकता है, जब N, X से विभाज्य हो।

इसलिए, यदि इनपुट A =7, B =4 जैसा है, तो आउटपुट 4 होगा क्योंकि N 210 है और भाजक 2, 3, 5, 7 हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एन:=1000005

• कारक:=आकार N की एक सरणी और 0 से भरें

• मुख्य विधि से, निम्न कार्य करें -

• मेरे लिए 2 से N की सीमा में, करें

  • अगर फ़ैक्टर [i] 0 के समान है, तो

    • i से N की श्रेणी में j के लिए, प्रत्येक चरण में i से अपडेट करें, करें

      • कारक [जे]:=कारक [जे / आई] + 1

• 1 से N की श्रेणी में i के लिए, करें

  • कारक [i]:=कारक [i] + कारक [i - 1];

• वापसी कारक[ए] - कारक[बी]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

N = 1000005
factors = [0] * N;
def get_prime_facts() :
   for i in range(2, N) :
      if (factors[i] == 0) :
         for j in range(i, N, i) :
            factors[j] = factors[j // i] + 1
   for i in range(1, N) :
      factors[i] += factors[i - 1];
get_prime_facts();
a = 7; b = 4;
print(factors[a] - factors[b])

इनपुट

7,4

आउटपुट

4