الأعداد الأولية ولعبة الحذف

طريقان إلى نفس الفكرة

قبل أن تبدأ

الفكرة الجوهرية

1غربال إراتوستينس

قائمة صح/خطأ لكل عدد، ونشطب المضاعفات بخطوة p:

def sieve(n):
    is_prime = [False, False] + [True] * (n - 1)
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
        p += 1
    return is_prime

flags = sieve(30)
print([i for i, ok in enumerate(flags) if ok])

2المجموع البادئ

بعد الغربال، prefix[i] يخزّن عدد الأوليات حتى i. أي سؤال «كم أولي حتى n؟» يصبح قراءة خانة:

def sieve(n):
    is_prime = [False, False] + [True] * (n - 1)
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
    return is_prime

questions = [5, 10, 1, 30]
flags = sieve(max(questions))
prefix, running = [], 0
for ok in flags:
    running += ok
    prefix.append(running)

for n in questions:
    print(n, "->", prefix[n], "primes")

3تمرين: من يفوز؟

لعبة: الأعداد من 1 إلى n على الطاولة. لاعبان يتناوبان، وفي كل دور يختار اللاعب عددًا أوليًا موجودًا ويحذفه مع كل مضاعفاته. من لا يجد عددًا أوليًا يخسر. لاحظ أن كل دور يحذف عددًا أوليًا واحدًا بالضبط (مضاعفاته ليست أولية)، فعدد الأدوار = عدد الأوليات حتى n. اكتب دالة تأخذ قائمة أسئلة (قيم n) وتعيد من فاز أكثر جولات، مستخدمًا الغربال والمجموع البادئ. اختبر: n = 1 لا أوليات فيخسر الأول.

مثال محلول

المسألة: n = 6. التحليل: الأوليات 2 و3 و5. الدور 1: الأول يحذف 2 (ومعه 4 و6). الدور 2: الثاني يحذف 3. الدور 3: الأول يحذف 5. الدور 4: الثاني لا يجد أوليًا. النتيجة: 3 أدوار، عدد فردي، الأول يفوز، ولم نحتج محاكاة: يكفي prefix[6] = 3.

خرافة مقابل حقيقة

أين تقابله في العمل

اختبر فهمك

بطاقات مراجعة سريعة

تحقق من فهمك