मान लीजिए हमारे पास पहले n प्राकृतिक संख्याओं {1..n} का एक सेट है। अमल और बिमल एक गेम खेल रहे हैं। गेम के नियम इस प्रकार हैं:
अमल हमेशा पहले खेलता है
प्रत्येक चाल के दौरान, वर्तमान खिलाड़ी सेट से एक अभाज्य संख्या p चुनता है। खिलाड़ी फिर p और उसके सभी गुणकों को सेट से हटा देता है।
जिसके पास कोई चाल नहीं होगी वह गेम हार जाएगा। यदि हमारे पास n है, तो हमें विजेता का नाम खोजना है।
तो, यदि इनपुट n = 5 है, तो आउटपुट अमल होगा, क्योंकि प्रारंभिक सेट {1,2,3,4,5} है। अब मान लीजिए अमल p = 2 चुनता है, और सेट से 2, 4 को हटा देता है, तो वर्तमान सेट {1,3,5} है, दो अभाज्य संख्याएं बची हैं, इसलिए बिमल उनमें से किसी को भी चुन सकता है लेकिन हटाने के लिए कोई शेष तत्व नहीं हैं और अंत में अमल एक और अभाज्य संख्या हटाकर गेम जीत जाता है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- primes := आकार 100000 की एक सरणी, प्रारंभ में सभी 0 हैं
- sieve := आकार 100000 की एक सरणी, प्रारंभ में सभी 0 हैं
- i को 2 से 99999 तक की रेंज में, करें
- यदि sieve[i], 0 के समान है, तो
- primes[i] := primes[i-1]+1
- j को i से 100000 तक, प्रत्येक चरण में i से अपडेट करते हुए, करें
- sieve[j] := i
- अन्यथा,
- primes[i] := primes[i-1]
- यदि sieve[i], 0 के समान है, तो
- मुख्य विधि से निम्न कार्य करें:
- "बिमल" लौटाएं यदि primes[n] विषम है अन्यथा "अमल"
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
primes = [0 for i in range(100001)] sieve = [0 for i in range(100001)] for i in range(2, 100000): if sieve[i] == 0: primes[i] = primes[i-1]+1 for j in range(i, 100001, i): sieve[j] = i else: primes[i] = primes[i-1] def solve(n): return "Bimal" if primes[n] % 2 == 0 else "Amal" n = 5 print(solve(n))
इनपुट
5
आउटपुट
Amal