Основы программирования

печать n первых простых чисел


Рассмотрим пример, использующий захват динамической памяти. Требуется ввести целое цисло n и напечатать n первых простых чисел. (Простое число - это число, у которого нет нетривиальных делителей.) Используем следующий алгоритм: последовательно проверяем все нечетные числа, начиная с тройки (двойку рассматриваем отдельно). Делим очередное число на все простые числа, найденные на предыдущих шагах алгоритма и не превосходящие квадратного корня из проверяемого числа. Если оно не делится ни на одно из этих простых чисел, то само является простым; оно печатается и добавляется в массив найденных простых.

Поскольку требуемое количество простых чисел n до начала работы программы неизвестно, невозможно создать массив для их хранения в статической памяти. Выход состоит в том, чтобы захватывать пространство под массив в динамической памяти уже после ввода числа n. Вот полный текст программы:

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

int main() { int n; // Требуемое количество простых чисел int k; // Текущее количество найденных простых чисел int *a; // Указатель на массив найденных простых int p; // Очередное проверяемое число int r; // Целая часть квадратного корня из p int i; // Индекс простого делителя bool prime; // Признак простоты

printf("Введите число простых: "); scanf("%d", &n); if (n <= 0) // Некорректное значение => return 1; // завершаем работу с кодом ошибки

// Захватываем память под массив простых чисел a = (int *) malloc(n * sizeof(int));

a[0] = 2; k = 1; // Добавляем двойку в массив printf("%d ", a[0]); // и печатаем ее

p = 3; while (k < n) {

// Проверяем число p на простоту r = (int)( // Целая часть корня sqrt((double) p) + 0.001 ); i = 0; prime = true; while (i < k && a[i] <= r) { if (p % a[i] == 0) { // p делится на a[i] prime = false; // => p не простое, break; // выходим из цикла } ++i; // К следующему простому делителю }

if (prime) { // Если нашли простое число, a[k] = p; // то добавляем его в массив ++k; // Увеличиваем число простых printf("%d ", p); // Печатаем простое число if (k % 5 == 0) { // Переход на новую строку printf("\n"); // после каждых пяти чисел } }

p += 2; // К следующему нечетному числу }

if (k % 5 != 0) { printf("\n"); // Перевести строку }

// Освобождаем динамическую память free(a); return 0; }

Пример работы данной программы:

Введите число простых: 50 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229



Содержание раздела