मान लीजिए हमारे पास पहले n प्राकृतिक संख्याओं का एक सेट है {1..n}। अमल और बिमल एक खेल खेल रहे हैं। खेल के नियम नीचे दिए गए हैं
-
अमल हमेशा पहले खेलता है
-
प्रत्येक चाल के दौरान, वर्तमान खिलाड़ी सेट से एक अभाज्य संख्या p का चयन करता है। इसके बाद खिलाड़ी सेट से p और उसके सभी गुणजों को हटा देता है।
-
जिसके पास कोई चाल नहीं है वह खेल हार जाएगा यदि हमारे पास n है, तो हमें विजेता का नाम खोजना होगा।
इसलिए, यदि इनपुट n =5 की तरह है, तो आउटपुट अमल होगा, क्योंकि प्रारंभिक सेट {1,2,3,4,5} है। अब अमल एक संख्या p =2 का चयन करता है, और सेट से 2, 4 को हटाता है, इसलिए वर्तमान सेट {1,3,5} है, दो अभाज्य संख्याएँ बची हैं, इसलिए बिमल उनमें से किसी का चयन कर सकता है लेकिन कोई शेष तत्व नहीं हैं हटाने के लिए और अंत में अमल एक और प्राइम को हटा देता है और गेम जीत जाता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- प्राइम्स:=आकार 100000 की एक सरणी, शुरू में सभी 0 हैं
- छलनी:=आकार 100000 की एक सरणी, शुरू में सभी 0 हैं
- 2 से 99999 की श्रेणी में i के लिए, करें
- यदि चलनी[i] 0 के समान है, तो
- प्राइम्स[i] :=primes[i-1]+1
- जे रेंज में i से 100000 के लिए, प्रत्येक चरण में i, do
- . द्वारा अपडेट करें
- छलनी[जे] :=मैं
- अन्यथा,
- प्राइम्स[i] :=primes[i-1]
- यदि चलनी[i] 0 के समान है, तो
- मुख्य विधि से निम्न कार्य करें -
- यदि primes[n] विषम है तो "Bimal" लौटाएं अन्यथा "Amal"
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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