شرح شامل لاختبار الأعداد الأولية بلغة C مع أمثلة عملية وخوارزميات فعّالة

1. المقدمة

تُستخدم لغة C على نطاق واسع في تطوير الأنظمة والأجهزة المدمجة وغيرها من المجالات نظرًا لقدرتها على إنشاء برامج سريعة وفعّالة. في هذه المقالة، سنشرح بالتفصيل كيفية تنفيذ “اختبار الأعداد الأولية” باستخدام لغة C.

العدد الأولي هو عدد طبيعي لا يقبل القسمة إلا على نفسه وعلى العدد 1 فقط. على سبيل المثال، 2 و3 و5 و7 هي أعداد أولية، بينما 4 و6 ليست كذلك. تلعب الأعداد الأولية دورًا مهمًا في تقنيات التشفير وحل المسائل الرياضية.

في هذه المقالة، سنوضح كيفية إنشاء برنامج أساسي لاختبار الأعداد الأولية بلغة C، ثم ننتقل إلى خوارزميات أكثر كفاءة. المقال مناسب للمبتدئين والمتوسطين في البرمجة، لذا نرجو متابعة القراءة حتى النهاية.

2. ما هو العدد الأولي؟

تعريف العدد الأولي

العدد الأولي (Prime Number) هو عدد طبيعي أكبر من 1 لا يقبل القسمة إلا على نفسه وعلى العدد 1 فقط.

أمثلة على الأعداد الأولية

فيما يلي أمثلة على أعداد أولية صغيرة:

• 2، 3، 5، 7، 11، 13، 17، 19، 23، 29

النقطة الجديرة بالملاحظة هي أن العدد 2 هو العدد الأولي الزوجي الوحيد، وجميع الأعداد الأولية الأخرى فردية.

أهمية الأعداد الأولية

الأعداد الأولية ليست مهمة من الناحية الرياضية فقط، بل تُستخدم أيضًا بكثرة في علوم الحاسوب وتقنيات التشفير. على وجه الخصوص، تُستَخدم أعداد أولية كبيرة في أنظمة الأمان المعتمدة على الخوارزميات التشفيرية.

العلاقة بين الأعداد الأولية ولغة C

نظرًا لأن لغة C تتيح عمليات حسابية صحيحة ومعالجة فعّالة، فهي مناسبة لإنشاء برامج لاختبار الأعداد الأولية التي تتعامل مع كميات كبيرة من البيانات. في القسم التالي، سنشرح طرقًا عملية لاختبار الأعداد الأولية باستخدام C.

3. طريقة اختبار الأعداد الأولية بلغة C

الخوارزمية الأساسية

الطريقة الأساسية لاختبار العدد الأولي تتكون من خطوتين:

1. إذا كان الرقم (n) أقل من 2، فهو ليس عددًا أوليًا.
2. قسمة (n) على جميع الأعداد الصحيحة من 2 حتى (√n)، وإذا كانت النتيجة بدون باقي، فهو ليس عددًا أوليًا.

تُعرف هذه الطريقة باسم “طريقة القسمة التجريبية”، وهي فعّالة كفاية للاختبارات الصغيرة.

مثال أساسي بلغة C

الكود التالي هو برنامج بسيط يحدد ما إذا كان العدد الذي يدخله المستخدم عددًا أوليًا:

#include <stdio.h>
#include <math.h>

// دالة اختبار العدد الأولي
int is_prime(int n) {
    if (n <= 1) return 0;  // الأعداد الأقل أو المساوية لـ 1 ليست أولية
    if (n == 2) return 1;  // 2 عدد أولي
    if (n % 2 == 0) return 0;  // الأعداد الزوجية (ما عدا 2) ليست أولية

    // فحص الأعداد الفردية فقط
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;  // إذا كان قابلاً للقسمة، فهو ليس أوليًا
    }
    return 1;  // عدد أولي
}

int main() {
    int num;

    // إدخال الرقم
    printf("أدخل عددًا صحيحًا: ");
    scanf("%d", &num);

    // عرض النتيجة
    if (is_prime(num))
        printf("%d هو عدد أولي.\n", num);
    else
        printf("%d ليس عددًا أوليًا.\n", num);

    return 0;
}

شرح الكود

1. تضمين ملفات الترويس

• <stdio.h>: مكتبة الإدخال والإخراج القياسية.
• <math.h>: مطلوبة لاستخدام دالة الجذر التربيعي sqrt.

1. الدالة is_prime

• إذا كان n <= 1، فليس عددًا أوليًا.
• العدد 2 يعتبر استثناءً كعدد أولي.
• استبعاد الأعداد الزوجية ما عدا 2.
• في الحلقة، يتم فحص الأعداد الفردية فقط لتقليل عدد العمليات.

1. الفحص حتى الجذر التربيعي

• يكفي الفحص حتى (√n) لأن العوامل تظهر بشكل متماثل حول الجذر التربيعي.

1. إدخال المستخدم وعرض النتيجة

• يتم إدخال العدد من المستخدم وفحصه ثم عرض النتيجة.

4. تقديم خوارزميات فعّالة

طرق تحسين السرعة

على الرغم من أن خوارزمية اختبار العدد الأولي الأساسية بسيطة، إلا أن حجم العمليات الحسابية يزداد مع الأعداد الكبيرة مما قد يؤدي إلى بطء التنفيذ. يمكن تحسين الأداء بالطرق التالية:

1. استبعاد الأعداد الزوجية

• جميع الأعداد الزوجية ما عدا 2 ليست أولية، لذا يتم فحص الأعداد الفردية فقط.

1. الفحص حتى الجذر التربيعي

• العوامل تكون متماثلة حول الجذر التربيعي، مما يسمح بتقليل نطاق الفحص إلى (√n) فقط.

1. إضافة فحوصات مسبقة

• التحقق مبكرًا من القابلية للقسمة على أعداد أولية صغيرة مثل 2 و3 و5 و7 لتقليل العمليات.

ما هي طريقة غربال إراتوستينس؟

غربال إراتوستينس هو خوارزمية فعّالة لإيجاد جميع الأعداد الأولية ضمن نطاق معين، ويعمل كالآتي:

1. التهيئة

• إنشاء قائمة بالأعداد واعتبارها جميعًا مرشحة لتكون أولية.

1. إزالة المضاعفات

• بدءًا من العدد 2، يتم وضع علامة على جميع مضاعفاته بأنها ليست أولية.

1. شرط الإيقاف

• يتوقف الفحص عندما يتجاوز العدد قيد الفحص الجذر التربيعي للحد الأعلى.

مثال على تطبيق غربال إراتوستينس بلغة C

الكود التالي يوضح تطبيق غربال إراتوستينس:

#include <stdio.h>
#include <stdbool.h>

#define MAX 1000  // الحد الأقصى للنطاق

void sieve_of_eratosthenes(int n) {
    bool prime[n + 1];  // مصفوفة للتحقق من الأعداد الأولية
    for (int i = 0; i <= n; i++)
        prime[i] = true;  // تهيئة جميع القيم إلى true

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;  // وضع علامة على المضاعفات بأنها ليست أولية
        }
    }

    // عرض النتائج
    printf("قائمة الأعداد الأولية:\n");
    for (int i = 2; i <= n; i++) {
        if (prime[i])
            printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int limit;
    printf("أدخل الحد الأقصى للبحث عن الأعداد الأولية: ");
    scanf("%d", &limit);

    if (limit < 2) {
        printf("الرجاء إدخال عدد أكبر أو يساوي 2.\n");
        return 1;
    }

    sieve_of_eratosthenes(limit);
    return 0;
}

شرح الكود

1. تهيئة المصفوفة prime[]

• يتم تعيين جميع العناصر إلى “true” كبداية.

1. إزالة المضاعفات

• يتم وسم جميع مضاعفات العدد الجاري فحصه بأنها ليست أولية.

1. الفحص حتى الجذر التربيعي

• يبدأ فحص المضاعفات من p² لتجنب العمليات غير الضرورية.

1. عرض النتائج

• يتم عرض جميع القيم التي بقيت “true” كأعداد أولية.

5. ملاحظات عند التنفيذ

1. التعامل مع الأعداد الكبيرة

المشكلة
في لغة C، يختلف حجم نوع البيانات int حسب البيئة، وغالبًا ما يكون الحد الأقصى في بيئة 32 بت حوالي 2,147,483,647. لذلك، عند التعامل مع أعداد أكبر، يجب اتخاذ الإجراءات التالية:

طرق المعالجة

1. استخدام long long int

• يدعم أعدادًا تصل إلى حوالي 9 كوينتيليون (9,223,372,036,854,775,807).

long long int num = 9223372036854775807LL;

2. استخدام مكتبات خارجية

• مثل مكتبة GMP (GNU MP) التي تدعم الأعداد الصحيحة ذات الدقة العالية.

#include <gmp.h>
mpz_t num;
mpz_init(num);

2. تحسين الأداء وتقليل التعقيد الحسابي

المشكلة
اختبار الأعداد الأولية قد يستهلك وقتًا كبيرًا خاصة عند التعامل مع بيانات ضخمة أو نطاقات واسعة.

طرق التحسين

1. استخدام التخزين المؤقت (Caching)

• حفظ نتائج الفحص لتجنب إعادة الحساب عند إدخال نفس القيم.

1. المعالجة المتوازية

• باستخدام الخيوط المتعددة أو OpenMP لزيادة سرعة التنفيذ.

#pragma omp parallel for
for (int i = 0; i < n; i++) {
    // معالجة متوازية
}

3. اختيار الخوارزمية المناسبة

• استخدام “القسمة التجريبية” للنطاقات الصغيرة، و”غربال إراتوستينس” للنطاقات الكبيرة.

3. أهمية معالجة الأخطاء

أمثلة على الأخطاء المحتملة

• إدخال غير صالح: مثل إدخال أعداد سالبة أو نصوص.
• تجاوز السعة (Overflow): إدخال أعداد أكبر من الحد المدعوم.

طرق المعالجة

1. التحقق من صحة الإدخال

• التأكد من أن الإدخال رقم صحيح قبل المعالجة.

int num;
printf("أدخل عددًا صحيحًا: ");
if (scanf("%d", &num) != 1) {
    printf("إدخال غير صالح.\n");
    return 1;
}

2. تقييد النطاق

• تحديد نطاق مسموح به وتجاهل القيم غير المناسبة.

3. منع تسرب الذاكرة

• تحرير الذاكرة قبل إنهاء البرنامج عند استخدام التخصيص الديناميكي.

4. قابلية القراءة والصيانة للكود

المشكلة
الكود المعقد يصعب قراءته وصيانته، حتى لو كان موجهًا للمبتدئين.

نصائح التحسين

1. تقسيم الكود إلى دوال

• فصل المهام إلى دوال منفصلة وفق مبدأ المسؤولية الواحدة.

1. إضافة التعليقات

• توضيح الهدف من كل جزء من الكود.

1. تسمية واضحة للمتغيرات

• استخدام أسماء مثل input_number أو is_prime_result بدلًا من أسماء عامة.

6. أمثلة على تشغيل الكود

في هذا القسم، سنعرض أمثلة على تشغيل برنامج اختبار الأعداد الأولية وبرنامج غربال إراتوستينس بلغة C.

مثال على برنامج اختبار الأعداد الأولية

الكود (إعادة عرض)

#include <stdio.h>
#include <math.h>

// دالة اختبار العدد الأولي
int is_prime(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;

    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num;
    printf("أدخل عددًا صحيحًا: ");
    scanf("%d", &num);

    if (is_prime(num))
        printf("%d هو عدد أولي.\n", num);
    else
        printf("%d ليس عددًا أوليًا.\n", num);

    return 0;
}

أمثلة تشغيل

أدخل عددًا صحيحًا: 17
17 هو عدد أولي.

أدخل عددًا صحيحًا: 18
18 ليس عددًا أوليًا.

أدخل عددًا صحيحًا: 1
1 ليس عددًا أوليًا.

أدخل عددًا صحيحًا: -5
-5 ليس عددًا أوليًا.

مثال على برنامج غربال إراتوستينس

الكود (إعادة عرض)

#include <stdio.h>
#include <stdbool.h>

#define MAX 1000

void sieve_of_eratosthenes(int n) {
    bool prime[n + 1];
    for (int i = 0; i <= n; i++)
        prime[i] = true;

    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    printf("قائمة الأعداد الأولية:\n");
    for (int i = 2; i <= n; i++) {
        if (prime[i])
            printf("%d ", i);
    }
    printf("\n");
}

int main() {
    int limit;
    printf("أدخل الحد الأقصى للبحث عن الأعداد الأولية: ");
    scanf("%d", &limit);

    if (limit < 2) {
        printf("الرجاء إدخال عدد أكبر أو يساوي 2.\n");
        return 1;
    }

    sieve_of_eratosthenes(limit);
    return 0;
}

مثال تشغيل

أدخل الحد الأقصى للبحث عن الأعداد الأولية: 50
قائمة الأعداد الأولية:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

7. الخلاصة

في هذه المقالة، شرحنا بالتفصيل كيفية اختبار الأعداد الأولية باستخدام لغة C، بدءًا من الخوارزميات الأساسية وحتى الطرق الأكثر كفاءة.

1. أهم النقاط

• العدد الأولي هو عدد لا يقبل القسمة إلا على نفسه وعلى العدد 1، وله أهمية في الرياضيات وتقنيات التشفير.
• قدمنا برنامجًا بسيطًا باستخدام “القسمة التجريبية” مع تحسين الفحص حتى الجذر التربيعي.
• استعرضنا خوارزمية غربال إراتوستينس التي تناسب النطاقات الكبيرة.
• ذكرنا ملاحظات هامة حول الأداء، الأخطاء المحتملة، وتحسين الكود.

2. خطوات التطوير المستقبلية

• تعلم خوارزميات أكثر تقدمًا مثل اختبار ميلر-رابين و AKS.
• تطبيقات في التشفير مثل خوارزمية RSA.
• استخدام المعالجة المتوازية و GPU لزيادة الأداء.
• تجربة الخوارزميات بلغات برمجة أخرى مثل Python أو C++.

3. كلمة أخيرة

اختبار الأعداد الأولية هو موضوع أساسي في البرمجة، لكنه يرتبط أيضًا بمجالات متقدمة مثل التشفير والخوارزميات الرياضية. نأمل أن تكون هذه المقالة قد ساعدتك على فهم الأساسيات بلغة C، وأن تكون خطوة أولى نحو تطوير مهاراتك في البرمجة والخوارزميات.