Рассмотрим один из алгоритмов поиска простых чисел, который называется: Решето Сундарама. Будет представлена реализация алгоритма на языке программирования Си, а также пример консольной программы, демонстрирующей работу алгоритма в действии.
Простое число — это число, которое делится само на себя и на единицу (простые числа: 2, 3, 5, 7, 11 и т.д.).
Решето Сундарама — это алгоритм для нахождения всех простых чисел до некоторого натурального числа N. Алгоритм был разработан индийским студентом С. П. Сундарамом в 1934 году.
Описание работы алгоритма:
Необходимо исключить из отрезка [1; N] все числа, которые представляются суммой вида:
переменные 
пробегают все натуральные значения, для которых выполняется условие 
, а именно индексы i и j меняются в пределах:
Каждое не исключенное число необходимо умножить на два и прибавить к нему единицу. В результате получится последовательность простых чисел в отрезке [3; 2N+1].
Ниже приведена реализация алгоритма Решето Сундарама на языке программирования Си. Функция Sundaram принимает в качестве аргумента целое число N.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void Sundaram (int N) { if (N > 0) { bool *exclude = (bool *)malloc((N + 1) * sizeof(bool)); for (int i = 1; i <= N; i++) exclude[i] = false; int a = (sqrtf(2 * N + 1) - 1) / 2; for (int i = 1; i <= a; i++) for (int j = i; j <= (N - i) / (2 * i + 1); j++) exclude[i + j + 2 * i * j] = true; //исключить printf("2 "); for (int i = 1; i <= N; i++) if (!exclude[i]) printf("%d ", i * 2 + 1); free(exclude); } } |
Также представляем вашему вниманию пример консольной программы на языке Си, которая считывает с клавиатуры целое число N и выводит на экран список простых чисел в отрезке [2; 2N+1].
|
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 |
#include <stdio.h> #include <malloc.h> #include <math.h> #include <conio.h> void Sundaram (int n); int main () { int N; printf("Input N: "); scanf_s("%d", &N); Sundaram(N); _getch(); return 0; } void Sundaram (int N) { if (N > 0) { bool *exclude = (bool *)malloc((N + 1) * sizeof(bool)); for (int i = 1; i <= N; i++) exclude[i] = false; int a = (sqrtf(2 * N + 1) - 1) / 2; for (int i = 1; i <= a; i++) for (int j = i; j <= (N - i) / (2 * i + 1); j++) exclude[i + j + 2 * i * j] = true; //исключить printf("2 "); for (int i = 1; i <= N; i++) if (!exclude[i]) printf("%d ", i * 2 + 1); free(exclude); } } |
Демонстрация работы программы:
Если вы хотите скачать исходник этой программы, то нажмите на кнопку ниже.
Скачать исходник
Смотрите также:
Поиск простых чисел. Решето Эратосфена на Си
Поделиться в соц. сетях: