পাইথনে সেট এলিমেন্ট রিমভাল গেমের বিজয়ী খুঁজে বের করা

প্রথম n প্রাকৃতিক সংখ্যা {1..n} সেটে আছে। আমল এবং বিমল গেম খেলছে। নিয়ম:

• আমল প্রথম খেলে।
• প্রতিটি মুভে একটি প্রাইম p বেছে নিয়ে p এবং এর সব গুণফল সেট থেকে বাদ দিতে হবে।
• যিনি মুভ দিতে পারবেন না সে হাবে।

n দেওয়া থাকলে বিজয়ীর নাম বের করতে হবে।

উদাহরণ

ইনপুট: n = 5

আউটপুট: Amal

সেট {1,2,3,4,5}। আমল ২ বেছে নিয়ে ২,৪ বাদ দিলে {1,3,5}। বিমল ৩ বা ৫ বেছে নিলে আমল বাকিটা নিয়ে জিতবে।

সমাধান পদ্ধতি

1. সিভ অফ এরাটোস্থেনিস দিয়ে ১ থেকে ১০০০০০ পর্যন্ত প্রাইম কাউন্ট প্রিকম্পিউট করুন।
2. primes[n] = n পর্যন্ত প্রাইমের সংখ্যা।
3. যদি primes[n] বিজোড় হয়: "Amal", অন্যথায় "Bimal"।

তত্ত্ব: প্রতিটি মুভে একটা প্রাইম বাদ যায়। মোট প্রাইম সংখ্যা বিজোড় হলে প্রথম খেলোয়া জিতবে।

পাইথন ইমপ্লিমেন্টেশন

primes = [0] * 100001
sieve = [0] * 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))  # আউটপুট: Amal

ইনপুট

5

আউটপুট

Amal