यह C17 प्रोग्राम परीक्षण विभाजन से संख्याओं की जाँच करता है और 1 से ऊपरी सीमा n तक की अभाज्य संख्याएँ सूचीबद्ध करता है। इसमें 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 = 5, 11, 17, ... के लिए i और i + 2 की जाँच होती है। भाजक के संभावित मान 6k - 1 और 6k + 1 के रूप में हैं, 6 के गुणज नहीं। इन रूपों की हर संख्या अभाज्य भी नहीं होती।
2. हर भाज्य संख्या का कोई अभाज्य गुणनखंड उसके वर्गमूल से बड़ा नहीं होता। इसलिए i <= num / i तक जाँच पर्याप्त है। धनात्मक पूर्णांकों के लिए यह i * i <= num वाला ही दायरा जाँचता है, लेकिन int के गुणन में अतिप्रवाह से बचाता है। फ़्लोटिंग-पॉइंट वर्गमूल निकालने की आवश्यकता नहीं है।
3. सीमा 2 से छोटी होने पर printPrimes केवल खाली पंक्ति छापता है। अन्यथा पहले 2 छापता है और फिर विषम संख्याओं की जाँच करता है। i > n - 2 होने पर जोड़ने से पहले लूप समाप्त होता है। इससे सीमा INT_MAX होने पर भी अंतिम i += 2 में अतिप्रवाह नहीं होता।
4. readLimit में fgets से पढ़ा जाता है, फिर strtol के रूपांतरण-अंत सूचक और ERANGE की जाँच होती है। int में बदलने से पहले मान का 0 से INT_MAX तक होना भी सुनिश्चित किया जाता है। isspace का तर्क पहले unsigned char में बदला जाता है। scanf("%d", &n) का वापसी मान अनदेखा करने पर असफल इनपुट के बाद अप्रारंभित n इस्तेमाल हो सकता है। रूपांतरण का परिणाम int की सीमा से बाहर हो तो यह मान लेना भी सही नहीं है कि उसे साधारण रूपांतरण-विफलता की तरह संभाला जाएगा।

उपयोग की सीमा

INT_MAX कार्यान्वयन पर निर्भर करता है। 32-बिट int के लिए यह 2,147,483,647 है, लेकिन C हर कार्यान्वयन में यही मान अनिवार्य नहीं करता। किसी ऊपरी सीमा को निरूपित कर पाना यह नहीं बताता कि वहाँ तक की सभी अभाज्य संख्याएँ जल्दी छप जाएँगी।

यह कार्यान्वयन परीक्षण विभाजन सीखने के लिए है। एक संख्या की जाँच में विभाजनों की अधिकतम संख्या उसके वर्गमूल के समानुपाती होती है। सभी संभावित संख्याओं को सूचीबद्ध करने के लिए O(n sqrt(n)) विभाजन एक मोटी ऊपरी सीमा है। यहाँ एक विभाजन को एक संक्रिया गिना गया है; यह बिट-जटिलता या मापा गया समय नहीं है। बड़े दायरे में सूची बनाने के लिए एराटोस्थनीज़ की छलनी पर विचार करें। यह क्रिप्टोग्राफ़िक अभाज्य संख्या जनरेटर नहीं है। बड़े पूर्णांकों की जाँच के लिए Miller–Rabin का लेख देखें।

C के इनपुट फ़ंक्शन और पूर्णांक अंकगणित के नियम WG14 के C11 समिति मसौदे N1570 के खंड 6.5, 7.4, 7.21.6.2, 7.21.7.2 और 7.22.1.4 में देखे जा सकते हैं।