В этой статье поговорим о нахождении простых чисел с помощью языка программирования C. Будем использовать алгоритм, который называется «Решето Эратосфена».
В начале определение. Простое число — это такое натуральное число, которое делится само на себя и на единицу.
Дано натуральное число n, которое больше или равно двум (n>=2). Необходимо найти все простые числа, которые не больше n, то есть нужно найти все простые числа, принадлежащие отрезку [2; n]. Для поиска этих чисел будем использовать алгоритм «Решето Эратосфена». Он заключается в следующем:
- Выпишем все числа от 2 до n.
- Первое простое число 2. Присвоим это значение переменной p.
- Зачеркнем все числа в списке кратные p.
- Найдем первое незачеркнутое число, которое больше p, и присвоим переменной p это число.
- Повторяем пункты 3 и 4 до тех пор, пока это возможно. Если для данного p нету кратных чисел в списке (ничего не зачеркнули), то вычисления также закончены.
Итак, на основе этого алгоритма пишем программу:
|
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 |
#include <stdio.h> #include <stdlib.h> #include <conio.h> int main () { int n, p; int *mass; bool flag; //"зачеркивали" ли число для данного p printf("Input n: "); scanf_s("%d", &n); if (n >= 2) { n = n - 1; //теперь n - это количесвтво чисел в массиве mass = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) mass[i] = i + 2; for (int i = 0; i < n; i++) { p = mass[i]; flag = false; for (int j = i + 1; j < n; j++) { if (!(mass[j] % p)) { for (int k = j; k < n - 1; k++) mass[k] = mass[k+1]; flag = true; n--; //уменьшаем, потому что чисел на одно стало меньше j--; //уменьшаем, для того чтобы снова проверить на кратность j-е число. Оно же теперь стало другим } } if (flag == false) break; } for (int i = 0; i < n; i++) printf("%d ", mass[i]); free(mass); } else printf("Error. n must be >= 2\n"); _getch(); return 0; } |
Прокомментируем код. Считываем число n (строка 11), проверяем больше ли оно или равно двум (строка 12), если это так, то выполняем поиск простых чисел, используя «Решето Эратосфена», иначе — выводим сообщение об ошибке.
Переменная bool flag (строка 9) необходима для контроля — «зачеркивали» ли мы число для данного p.
Рассмотрим поиск простых чисел. Выделим память под массив с числами (строка 15) и заполним его (16-17). Перебираем числа (18-34), проверяя кратны ли они текущему p, если нашли такое число, то сдвигаем все стоящие справа от него числа на единицу влево, тем самым, затирая («зачеркивая») это число. Так проверяем все числа. Если для данного p ни одно число не было «зачеркнуто», то работа программы завершена, все числа в массиве — простые. Освобождаем память (37).
Исходник программы можно скачать внизу страницы. Демонстрация работы программы:
Смотрите также:
Поиск простых чисел. Решето Сундарама на Си
Поделиться в соц. сетях: