Эта программа на 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 зависит от реализации. Для 32-битного int он равен 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.