الخوارزميات العددية

القواسم والأعداد الأولية

القسمة التجريبية

يكون العدد الصحيح $n \geq 2$ أوليًا إذا كان قاسماه الموجبان الوحيدان هما 1 و$n$؛ وإذا كان له قاسم آخر فهو مؤلَّف؛ أما 0 و1 فليسا هذا ولا ذاك. ويوحي التعريف فورًا بخوارزمية: تجربة كل مرشَّح $d$ بين 2 و$n - 1$، والحكم على العدد بأنه مؤلَّف حالما يقسمه أحدها. وهي حلقة القاسم الأصغر من الدرس الحلقات، وهي صحيحة. غير أنها، مع عدد أولي من عشرة أرقام، تُجري قرابة عشرة مليارات قسمة، وكلها تقريبًا بلا فائدة، للسبب الآتي.

ومن ذلك يلزم أن عدد القسمات ينخفض من نحو $n$ إلى نحو $\sqrt{n}$: فمع $n$ قريب من ملياري، ينخفض من ملياري قسمة إلى ستة وأربعين ألفًا. ويستعمل البرنامج نمط العَلَم من الدرس تصميم حلقات صحيحة: يبدأ isPrime صادقًا، وتُطفئه الحلقة إذا وجدت قاسمًا.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("العدد {} أولي", n);    } else {        std::println("العدد {} ليس أوليًا", n);    }}

2147483647

العدد 2147483647 أولي

ثلاثة قرارات تستحق التعليق. يُهيَّأ العَلَم بـn >= 2، فيُحكم على 0 و1 والأعداد السالبة بأنها غير أولية دون دخول الحلقة: ونسيان هذه الحالة هو الخطأ النموذجي، لأنه مع $n = 1$ لا تُجري الحلقة أي جولة، فيحكم البرنامج بأن 1 أولي. وشرط for له جزءان: العَلَم، الذي يوقف الحلقة عند أول قاسم، والحدّ. والحدّ مكتوب d <= n / d، وهو، للأعداد الصحيحة الموجبة، مكافئ لـ$d^2 \leq n$ (فالقسمة الصحيحة تبتر الكسر، لكن $d$ لا يتجاوز خارج القسمة المبتور بالضبط حين لا يتجاوز $n/d$، لأن $d$ عدد صحيح). والعدد المُدخل، $2^{31} - 1$، هو أكبر قيمة من نوع int، وهو أولي؛ ويحسم البرنامج ذلك بـ$46\,339$ باقيًا، هي بواقي قسمته على المرشَّحات من 2 إلى $46\,340$.

لامتغير الحلقة هو: لا يقسم أيُّ عدد صحيح من 2 إلى $d - 1$ العددَ $n$، ما دام العَلَم صادقًا. وهو صحيح عند الدخول، حين تكون الفترة من 2 إلى 1 خالية؛ ويُحفظ، لأنه إذا لم يقسم $d$ العددَ $n$ فإن الفترة تزداد بعدد لا يقسمه؛ وعند الخروج والعَلَم صادق، يقول اللامتغير والشرط الكاذب، $d^2 > n$، معًا إن أيَّ مرشَّح حتى $\sqrt{n}$ لا يقسم $n$، وهذا ما تقتضيه القضية. والمتغاير هو عدد المرشَّحات الباقية للتجربة، أي عدد الأعداد الصحيحة بين $d$ و$\sqrt{n}$: ينقص واحدًا في كل جولة ولا ينزل تحت الصفر.

الشرط الذي يفيض

الطريقة الطبيعية لكتابة الحدّ هي d * d <= n، وهي خطأ. فمع المُدخل نفسه تصل الحلقة إلى $d = 46\,341$، وحينئذ يتجاوز حاصل الضرب $46\,341^2 = 2\,147\,488\,281$ القيمةَ العظمى لـint.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("أولي؟ {}", isPrime);}

2147483647

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

يوقف كاشف السلوك غير المعرَّف البرنامج عند حاصل الضرب. ومن دونه، يكون فيضان الأعداد ذات الإشارة سلوكًا غير معرَّف، ولا يقول المعيار ماذا يحدث. وما يُلاحَظ مع GCC على Linux، مع التحسين ومن دونه، مفيد للتعلم: يلتفّ حاصل الضرب فيصير سالبًا أو أصغر من $n$، ولأنه لا توجد قيمة من نوع int تتجاوز القيمة العظمى، فإن الشرط d * d <= n لا يكفّ عن التحقق أبدًا؛ وتظل الحلقة تجرّب المرشَّحات نحو ملياري جولة، حتى تبلغ $d = n$، الذي يقسم $n$، فيحكم البرنامج بأن عددًا أوليًا مؤلَّف. فخطأ الفيضان لا يظهر في صورة فيضان، بل في صورة جواب خاطئ. أما الصورة d <= n / d فلا يمكن أن تفيض، لأنها تقسم بدل أن تضرب؛ وقد عرض الدرس البتات والمكتبة الرياضية مخرجًا آخر، هو حساب الحدّ مرة واحدة بـstd::sqrt، لكن دقة الحدّ تتوقف حينئذ على تقريب الفاصلة العائمة، والقسمة الصحيحة لا تعاني هذه المشكلة.

يبرهن الدرس «الأعداد الأولية والمبرهنة الأساسية في الحساب»، من دورة الجبر والهندسة 1، على أن كل عدد صحيح أكبر من 1 هو حاصل ضرب أعداد أولية بطريقة واحدة فقط؛ والقسمة التجريبية هي أقصر طريق لإيجاد هذا الحاصل، بقسمة $n$ على كل قاسم يُعثر عليه ومتابعة العمل بخارج القسمة.