ALGORITHMS
Добавлен Msey,
опубликован
Простое число — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x. К примеру, 5 — простое число, а 6 не является простым числом, так как, помимо 1 и 6, также делится на 2 и на 3.
Последовательность простых чисел начинается так:
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.....
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.....
Решето Сундарама — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа n. Разработан индийским студентом Сундарамом в 1934 году.
Алгоритм предусматривает исключение из ряда натуральных чисел от 1 до N всех чисел вида:
i+j+2ij
где индексы i <= j пробегают все натуральные значения, для которых i+j+2ij<=N, а затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все простые числа в отрезке [1,2N+1].
i+j+2ij
где индексы i <= j пробегают все натуральные значения, для которых i+j+2ij<=N, а затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все простые числа в отрезке [1,2N+1].
Обоснование
Алгоритм работает с нечётными натуральными числами большими единицы, представленными в виде 2m+1, где m является натуральным числом.
Если число 2m+1 является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть:
2m+1=(2i+1)(2j+1), где i и j — натуральные числа, что также равносильно соотношению:
m=2ij+i+j
m=2ij+i+j
Таким образом, если из ряда натуральных чисел исключить все числа вида 2ij+i+j <= 1, то для каждого из оставшихся чисел m число 2m+1 обязано быть простым. И, наоборот, если число 2m+1 является простым, то число m невозможно представить в виде 2ij+i+j и, таким образом, m не будет исключено в процессе работы алгоритма.
Алгоритм
#include <stdio.h>
int main(void) {
int i,j,n,ind;
scanf("%d",&n);
char a[n+1];
for (i=1; i<=n; i++)
a[i]=1;
for(i=1;2*i*(i+1)<n;i++)
for(j=i;ind=2*i*j+i+j,ind<=n;j++)
a[ind]=0;
for(i=1;i<=n;i++)
if(a[i])
printf("%d ",2*i+1);
return 0;
}
`
ОЖИДАНИЕ РЕКЛАМЫ...
Комментарии пока отсутcтвуют.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.