1. قاعدة الجذر التربيعي

لاختبار أولية عدد طبيعي $n$ ($n > 1$)، يكفي اختباره بالقسمة على جميع الأعداد الأولية $p$ التي تحقق الشرط:

$p \le \sqrt{n}$

فإذا كان $n$ لا يقبل القسمة على أي من هذه الأعداد الأولية، فهو عدد أولي.

2. غربال إراتوستين

خوارزمية لعزل الأعداد الأولية الأصغر من عدد معين $N$، وتعتمد على الخطوات التالية:

1. كتابة قائمة الأعداد الطبيعية من $2$ إلى $N$.

2. البدء بأول عدد أولي ($2$) وشطب جميع مضاعفاته في القائمة.

3. الانتقال إلى العدد التالي غير المشطوب وشطب جميع مضاعفاته.

4. تكرار العملية حتى الوصول إلى الأعداد التي لا تتجاوز $\sqrt{N}$.

مثال تطبيقي: اختبار أولية العدد 97

لدينا $\sqrt{97} \approx 9.8$، فالأعداد الأولية التي لا تتجاوز $9.8$ هي: $2، 3، 5، 7$.

اختبار القابلية للقسمة على هذه الأعداد:

• $97$ لا يقبل القسمة على $2$ (لأنه فردي).

• $97$ لا يقبل القسمة على $3$ (لأن $9+7=16$ ليس من مضاعفات $3$).

• $97$ لا يقبل القسمة على $5$ (لأن رقم الآحاد ليس $0$ أو $5$).

• $97 = 7 \times 13 + 6$ (الباقي غير معدوم، فلا يقبل القسمة على $7$).

النتيجة: العدد $97$ أولي.

---