Реализация алгоритма - Решето Сундарама

Количество просмотров: 434

Решето Сундарама — детерминированный алгоритм нахождения всех простых чисел. Алгоритм работает с нечётными натуральными числами большими единицы, представленными в виде 2m+1, где m является натуральным числом. Допустим необходимо получить все простые числа до некоторого N, тогда выходными данными будут все простые числа от 2 до 2N+1. Решето Сундарама из ряда натуральных чисел, не превышающих N, исключает числа вида

где
а оставшиеся числа N умножаются на 2 и к результату прибавляется 1. Итоговое множество будет содержать числа: 2, 3, …, 2N+1.

int A[1000], // 
		N=20,   // граница простых чисел
		i, j, 
		count=0, // счетчик числа простых чисел
		l=1;
		// заполняем массив чисел размерностью N нулями
		for (i=1; i<=2*N; i++) 
			A[i]=0;
		// решето Сундарама, вычеркиваем(т.е. приравниваем 1 элементы, не явл. простыми)
		i=1; 
		j=1;
		while ((2*i*j+i+j)<=N)
		{
			while (j<=(N-i)/(2*i+1))
			{
				A[2*i*j+i+j]=1;
				j++;
			}
			i++;
			j=i;
		}
		// подсчитываем число единиц
		for (i=1; i<=N; i++)
			if (A[i]==0) 
				count++;
		// создаем вектор простых чисел
		vector<int> massiv(count+1);
		// вычисляем простые числа, получая ряд до 2N+1 и сохраняем в созданный вектор
		massiv[0]=2;
		for (i=1; i<=N; i++)
			if (A[i]==0) 
			{	
				A[i]=2*i+1;
				massiv[l]=A[i];
				cout<<massiv[l]<<' ';
                l++;
            }


comments powered by HyperComments

© 2015-2018 Goodweb.me --- Карта сайта --- info@goodweb.me

Наверх