يستخدم برنامج C17 هذا القسمة التجريبية لاختبار الأعداد وسرد الأعداد الأولية من 1 إلى الحد الأعلى n شاملًا هذا الحد. العدد الأولي عدد صحيح لا يقل عن 2، لذلك لا تظهر أعداد أولية عندما يكون الحد 0 أو 1. أدخل عددًا صحيحًا عشريًا واحدًا من 0 إلى INT_MAX.

الكود

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <errno.h>
#include <limits.h>
#include <ctype.h>
#include <string.h>

bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;

    for (int i = 5; i <= num / i; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
}

void printPrimes(int n) {
    if (n < 2) {
        putchar('\n');
        return;
    }
    printf("2");
    for (int i = 3; i <= n; ) {
        if (isPrime(i)) printf(" %d", i);
        if (i > n - 2) break;
        i += 2;
    }
    putchar('\n');
}

bool readLimit(int *n) {
    char line[128];
    if (fgets(line, sizeof line, stdin) == NULL) return false;
    if (strchr(line, '\n') == NULL) {
        int next = getchar();
        if (next != '\n' && next != EOF) return false;
        if (ferror(stdin)) return false;
    }

    errno = 0;
    char *end;
    long value = strtol(line, &end, 10);
    if (end == line || errno == ERANGE || value < 0 || value > INT_MAX)
        return false;
    while (isspace((unsigned char)*end)) ++end;
    if (*end != '\0') return false;
    *n = (int)value;
    return true;
}

int main(void) {
    int n;
    printf("أدخل الحد الأعلى (من 0 إلى %d): ", INT_MAX);
    fflush(stdout);
    if (!readLimit(&n)) {
        fprintf(stderr, "إدخال غير صالح. أدخل عددًا صحيحًا واحدًا من 0 إلى %d.\n", INT_MAX);
        return EXIT_FAILURE;
    }
    printf("الأعداد الأولية من 1 إلى %d:\n", n);
    printPrimes(n);
    return EXIT_SUCCESS;
}

الترجمة البرمجية ومثال التشغيل

احفظ البرنامج باسم primes.c. في بيئة يتوفر فيها GCC، نفّذ gcc -std=c17 -Wall -Wextra -O2 primes.c -o primes ثم ./primes. عند إدخال 30، يظهر عنوان يتبعه السطر التالي:

1

2 3 5 7 11 13 17 19 23 29

الحد 2 ينتج 2، أما 0 أو 1 فينتج سطرًا فارغًا. يُقرأ الإدخال كسطر نصي واحد لا يتجاوز 127 بايت، دون احتساب محرف السطر الجديد. تُقبل محارف الفراغ في البداية والنهاية، وكذلك علامة + في البداية. القيم السالبة والأسطر الفارغة والنصوص التي لا تمثل عددًا صحيحًا والقيم خارج النطاق والأسطر الطويلة جدًا وإخفاقات القراءة تؤدي إلى رسالة خطأ وإنهاء البرنامج. يُعالَج السطر الأول فقط، ولا تُستخدم الأسطر اللاحقة.

آلية الاختبار ومعالجة الإدخال

1. تعيد isPrime القيمة خطأ للأعداد التي لا تتجاوز 1، وصحيح للعددين 2 و3. وتعيد خطأ لبقية مضاعفات 2 أو 3. ثم تختبر i وi + 2 للقيم i = 5, 11, 17, .... القواسم المرشحة من الشكل 6k - 1 أو 6k + 1، وليست مضاعفات 6. وليس كل عدد من هذين الشكلين أوليًا.
2. لكل عدد مؤلف قاسم أولي لا يتجاوز جذره التربيعي؛ لذا يكفي مواصلة الاختبار ما دام i <= num / i. للأعداد الصحيحة الموجبة، يغطي هذا الشرط النطاق نفسه الذي يغطيه i * i <= num، مع تجنب تجاوز سعة الضرب في النوع int. ولا حاجة إلى حساب جذر تربيعي باستخدام الفاصلة العائمة.
3. تطبع printPrimes سطرًا فارغًا فقط عندما يكون الحد أقل من 2. وإلا تطبع 2 أولًا، ثم تختبر المرشحين الفرديين. إذا تحقق i > n - 2، تنتهي الحلقة قبل الجمع، مما يمنع تجاوز السعة في آخر i += 2 حتى عندما يكون الحد INT_MAX.
4. تقرأ readLimit الإدخال بواسطة fgets، وتفحص مؤشر نهاية التحويل وERANGE الناتجين عن strtol، ثم تتحقق من أن القيمة ضمن النطاق من 0 إلى INT_MAX قبل تحويلها إلى int. وتحوّل وسيط isspace أولًا إلى unsigned char. تجاهل القيمة المعادة من scanf("%d", &n) قد يؤدي إلى استخدام n غير مهيأ بعد إخفاق الإدخال. ولا يجوز أيضًا افتراض أن نتيجة تحويل خارج نطاق int ستُعامل كمجرد إخفاق عادي في التحويل.

نطاق الاستخدام

تعتمد INT_MAX على التنفيذ. في حالة int ذي 32 بت، تساوي 2,147,483,647، لكن C لا تفرض هذه القيمة على جميع التنفيذات. القدرة على تمثيل حد أعلى لا تعني أن سرد جميع الأعداد الأولية حتى ذلك الحد سيكون سريعًا.

هذا التنفيذ مخصص لتعلّم القسمة التجريبية. عند اختبار عدد واحد، يُحد عدد عمليات القسمة من الأعلى بمقدار يتناسب مع جذره التربيعي. ولسرد جميع المرشحين، يمكن استخدام O(n sqrt(n)) عملية قسمة كحد أعلى تقريبي. تُحسب كل قسمة هنا كعملية واحدة؛ وهذا ليس تعقيدًا على مستوى البتات ولا زمنًا مقاسًا. لسرد الأعداد الأولية في نطاق كبير، يمكن النظر في غربال إراتوستينس. هذا البرنامج ليس مولّدًا للأعداد الأولية لأغراض التشفير. لاختبار أعداد صحيحة كبيرة، انظر مقال ميلر–رابين.

يمكن الرجوع إلى قواعد دوال الإدخال وحساب الأعداد الصحيحة في C ضمن الأقسام 6.5 و7.4 و7.21.6.2 و7.21.7.2 و7.22.1.4 من مسودة لجنة C11 ذات الرقم N1570 من WG14.