मान लीजिए हमारे पास दो संख्याएं P और Q हैं और वे एक संख्या N = (P!/Q!) बनाते हैं। हमें N को 1 तक कम करना है अधिकतम संभव ऑपरेशन करके। प्रत्येक ऑपरेशन में, कोई N को N/X से बदल सकता है जब N, X से विभाज्य हो। हम अधिकतम ऑपरेशन की संख्या वापस करेंगे जो संभव हो सकती है।
तो, यदि इनपुट A = 7, B = 4 की तरह है, तो आउटपुट 4 होगा क्योंकि N 210 है और भाजक 2, 3, 5, 7 हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
N := 1000005
factors := N आकार की एक सरणी और 0 से भरें
मुख्य विधि से, निम्नलिखित करें -
i के लिए 2 से N की सीमा में, करें
यदि factors[i], 0 के समान है, तो
j के लिए i से N की सीमा में, प्रत्येक चरण में i से अपडेट करें, करें
factors[j] := factors[j / i] + 1
i के लिए 1 से N की सीमा में, करें
factors[i] := factors[i] + factors[i - 1];
factors[a] - factors[b] वापस करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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
