Как получить список простых чисел в запросе

Поиск простых чисел с помощью запроса (решение тестового задания).

Описание
Подробнее

Описание

Что может быть проще простых чисел ? По определению, целое число называется простым, если оно не может быть представлено, как произведение двух меньших чисел. Единственное четное простое число — 2. Все остальные простые числа нечетные. Самый древний алгоритм поиска простых чисел получил название "решето Эратосфена". Это известная история и останавливаться на ней не будем. Сразу перейдем к заявленной теме, а именно, поиску простых чисел с помощью запроса на встроенном языке платформы 1С:Предприятие. Исходным объектом для поиска будет таблица натуральных чисел в диапазоне от 1 до заданного верхнего предела. Подобную таблицу, можно формировать в запросе , но мы упростим себе жизнь и заполним её с помощью операторов встроенного языка.

тз=новый таблицазначений;
тз.Колонки.Добавить("НатуральноеЧисло",новый ОписаниеТипов("Число"));
для н=1 по ВерхнийПредел цикл
  приемник=тз.Добавить();
  приемник.НатуральноеЧисло=н;
конеццикла;

Рассмотрим первый алгоритм. Построим соединение двух одинаковых таблиц, сформированных на первом этапе. В характеристиках связи зададим условие, что левый множитель меньше или равен правому, плюс потребуем,чтобы произведение этих чисел было меньше максимального числа в исходной таблице. Для каждой образованной пары чисел вычислим произведение.Ниже приведен пример для набора чисел меньше 9. Исходная таблица

НатуральноеЧисло
1
2
3
4
5
6
7
8
9

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

Левое	Правое	Произведение
1	1	1
1	2	2
2	2	4
1	3	3
2	3	6
3	3	9
1	4	4
2	4	8
1	5	5
1	6	6
1	7	7
1	8	8
1	9	9

Исходная таблица содержала 9 строк, итоговая 13. Среди чисел в колонке Произведение есть повторяющиеся. Это числа 4,6 и 9. Числа 1,2,3,5,7 встречаются только один раз. Единицу из этого ряда надо исключить. Оставшиеся четыре числа будут первыми в ряду простых чисел. Приведем текст запроса:

    запрос=новый запрос();
	запрос.МенеджерВременныхТаблиц=новый МенеджерВременныхТаблиц;
	запрос.Параметры.Вставить("Числа",тз);
	запрос.Параметры.Вставить("ВерхняяГраница",тз[тз.Количество()-1].НатуральноеЧисло);
	запрос.Текст="ВЫБРАТЬ
	             |	Числа.НатуральноеЧисло КАК НатурЧисло
	             |ПОМЕСТИТЬ ВТ
	             |ИЗ
	             |	&Числа КАК Числа
	             |;
	             |
	             |
	             |ВЫБРАТЬ
	             |	Левый.НатурЧисло * Правый.НатурЧисло КАК НатуральноеЧисло
	             |ПОМЕСТИТЬ мПростыеЧисла
	             |ИЗ
	             |	ВТ КАК Левый
	             |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ КАК Правый
	             |		ПО (Левый.НатурЧисло * Правый.НатурЧисло <= &ВерхняяГраница)
	             |			И Левый.НатурЧисло <= Правый.НатурЧисло
	             |
	             |СГРУППИРОВАТЬ ПО
	             |	Левый.НатурЧисло * Правый.НатурЧисло
	             |
	             |ИМЕЮЩИЕ
	             |	Количество(*) = 1
	             |;
	             |
	             |
	             |ВЫБРАТЬ
	             |	КОЛИЧЕСТВО(мПростыеЧисла.НатуральноеЧисло) - 1 КАК НатуральноеЧисло
	             |ИЗ
	             |	мПростыеЧисла КАК мПростыеЧисла";

Запрос возвращает количество простых чисел в первоначальном диапазоне.Приведенный алгоритм отличается простотой, но увы, слишком медленный. Постараемся придумать, что-то быстрее.

Как проверить, что число А делится без остатка на число Б. Во встроенном языке есть оператор %, который возвращает остаток от деления. В языке запросов такая опция отсутствует. Поэтому воспользуемся следующим приемом :

ВЫРАЗИТЬ(A/Б КАК ЧИСЛО(19,0))*Б = A

Если это выражение истинно, то Б является делителем числа А. Идея запроса следующая. Организуем внутреннее соединение исходной таблицы со своей копией, где в качестве условия выступает представленная выше проверка на делимость. Понятно, что число Б должно быть меньше числа А. Более того, число Б должно быть меньше корня квадратного из А. Квадратный корень в запросе мы вычислить не можем, но мы можем найти целое приближение к квадратному корню.

Сформируем таблицу с квадратами наших исходных чисел.Теперь соединим данную таблицу с исходной. Полученную набор сгруппируем по исходным числам, а для квадратов применим функцию МИНИМУМ(). Текст запроса приведен ниже:

                 ВЫБРАТЬ
	             |	Числа.НатуральноеЧисло КАК Н
	             |ПОМЕСТИТЬ ВТ
	             |ИЗ
	             |	&Числа КАК Числа
	             |;
	             |
	             |///////////
	             |ВЫБРАТЬ
	             |	ВТ.Н * ВТ.Н КАК Квадрат,
	             |	ВТ.Н КАК Н
	             |ПОМЕСТИТЬ мКвадраты
	             |ИЗ
	             |	ВТ КАК ВТ
	             |ГДЕ
	             |	ВТ.Н * ВТ.Н <= &ВерхняяГраница
	             |;
	             |
	             |//////////
	             |ВЫБРАТЬ
	             |	ВТ.Н КАК Н,
	             |	ВЫБОР
	             |		КОГДА ВТ.Н = 1
	             |			ТОГДА 0
	             |		КОГДА ВТ.Н = 2
	             |			ТОГДА 1
	             |		ИНАЧЕ МИНИМУМ(мКвадраты.Н)
	             |	КОНЕЦ КАК Корень
	             |ПОМЕСТИТЬ мКорни
	             |ИЗ
	             |	ВТ КАК ВТ
	             |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ мКвадраты КАК мКвадраты
	             |		ПО ВТ.Н <= мКвадраты.Квадрат
	             |
	             |СГРУППИРОВАТЬ ПО
	             |	ВТ.Н
	             |;

Во временной таблице мКорни в колонке Н содержится число из исходного набора, а в колонке Корень, минимальное число,квадрат которого больше или равен Н. А теперь соберем все вместе:

    запрос=новый запрос();
	запрос.МенеджерВременныхТаблиц=новый МенеджерВременныхТаблиц;
	запрос.Параметры.Вставить("Числа",тз);

	
	запрос.Текст="ВЫБРАТЬ
	             |	Числа.НатуральноеЧисло КАК Н
	             |ПОМЕСТИТЬ ВТ
	             |ИЗ
	             |	&Числа КАК Числа
	             |;
	             |
	             |/////////////////
	             |ВЫБРАТЬ
	             |	ВТ.Н * ВТ.Н КАК Квадрат,
	             |	ВТ.Н КАК Н
	             |ПОМЕСТИТЬ мКвадраты
	             |ИЗ
	             |	ВТ КАК ВТ
	             |;
	             |
	             |///////////////
	             |ВЫБРАТЬ
	             |	ВТ.Н КАК Н,
	             |	ВЫБОР
	             |		КОГДА ВТ.Н = 1
	             |			ТОГДА 0
	             |		КОГДА ВТ.Н = 2
	             |			ТОГДА 1
	             |		ИНАЧЕ МИНИМУМ(мКвадраты.Н)
	             |	КОНЕЦ КАК Корень
	             |ПОМЕСТИТЬ мКорни
	             |ИЗ
	             |	ВТ КАК ВТ
	             |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ мКвадраты КАК мКвадраты
	             |		ПО ВТ.Н <= мКвадраты.Квадрат
	             |
	             |СГРУППИРОВАТЬ ПО
	             |	ВТ.Н
	             |;
	             |
	             |/////////////
	             |ВЫБРАТЬ
	             |	мКорни.Н КАК Н,
	             |	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ Делители.Н) КАК КолВоДелителей
	             |ПОМЕСТИТЬ мТаблицаПростыхЧисел
	             |ИЗ
	             |	мКорни КАК мКорни
	             |		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ КАК Делители
	             |		ПО мКорни.Корень >= Делители.Н
	             |			И ((ВЫРАЗИТЬ(мКорни.Н / Делители.Н КАК ЧИСЛО(19, 0))) * Делители.Н = мКорни.Н)
	             |
	             |СГРУППИРОВАТЬ ПО
	             |	мКорни.Н
	             |
	             |ИМЕЮЩИЕ
	             |	КОЛИЧЕСТВО(Делители.Н) = 1
	             |;
	             |
	             |//////////
	             |ВЫБРАТЬ
	             |	КОЛИЧЕСТВО(мТаблицаПростыхЧисел.Н) КАК НатуральноеЧисло
	             |ИЗ
	             |	мТаблицаПростыхЧисел КАК мТаблицаПростыхЧисел";

Любопытно проверить, как различаются скорость выполнения первого и второго запроса (время в миллисекундах):

Верхняя граница	1000	2000	3000	4000	5000
Вариант 1	492	795	1229	2314	3061
Вариант 2	651	954	1644	2955	4364

Видим, что первый вариант запроса отрабатывает быстрее. Для второго можно "проредить" исходные данные, а именно убрать все четные числа кроме двойки (это уже элемент алгоритма "решето Эратосфена").

          тз=новый таблицазначений;
	      тз.Колонки.Добавить("НатуральноеЧисло",новый ОписаниеТипов("Число"));
		  приемник=тз.Добавить();
		  приемник.НатуральноеЧисло=1;
		  приемник=тз.Добавить();
		  приемник.НатуральноеЧисло=2;
		  для н=3 по ЭтотОбъект.UpLimit цикл
			  приемник=тз.Добавить();
			  приемник.НатуральноеЧисло=н;
			  н=н+1;
		  конеццикла;

Очевидно, что после такой операции скорость должна увеличиться, что и показывают замеры (время в миллисекундах):

Верхняя граница	1000	2000	3000	4000	5000
Вариант 1	492	795	1229	2314	3061
Вариант 2 (ускоренный)	268	842	1163	1373	1587

Посмотрев решения от Сергея (ildarovich) , решил добавить экзотику в виде решета Аткина. Максимальное значение верхней границы в приведенном примере — 100 000. Параметры запроса — Граница и КореньИзГраницы. Все простые числа <= 100 000 программа находит за 3 сек. Результат хуже чем у Сергея (ildarovich), но тоже неплохой.

ВЫБРАТЬ
	0 КАК Х
ПОМЕСТИТЬ Регистр1

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	1

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	2

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	3

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	4

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	5

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	6

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	7

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	8

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	9
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Младшие.Х + 10 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр2
ИЗ
	Регистр1 КАК Младшие,
	Регистр1 КАК Старшие
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Младшие.Х + 100 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр4
ИЗ
	Регистр2 КАК Младшие,
	Регистр2 КАК Старшие
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Младшие.Х + 10000 * Старшие.Х + 1 КАК Н
ПОМЕСТИТЬ Числа
ИЗ
	Регистр4 КАК Младшие,
	Регистр1 КАК Старшие
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Числа.Н КАК Н,
	ВЫБОР
		КОГДА Числа.Н < &КореньИзГраницы
			ТОГДА Числа.Н * Числа.Н
		ИНАЧЕ 0
	КОНЕЦ КАК КвадратН
ПОМЕСТИТЬ ВТ
ИЗ
	Числа КАК Числа
ГДЕ
	Числа.Н <= &Граница

ИНДЕКСИРОВАТЬ ПО
	Н
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	4 * X.КвадратН + Y.КвадратН КАК Н,
	КОЛИЧЕСТВО(*) КАК КолВо
ПОМЕСТИТЬ Т1
ИЗ
	ВТ КАК X
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ КАК Y
		ПО (X.КвадратН > 0)
			И (Y.КвадратН > 0)
			И (4 * X.КвадратН + Y.КвадратН <= &Граница)

СГРУППИРОВАТЬ ПО
	4 * X.КвадратН + Y.КвадратН

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(*) В (1, 3, 5, 7, 9)

ИНДЕКСИРОВАТЬ ПО
	Н
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	3 * X.КвадратН + Y.КвадратН КАК Н,
	КОЛИЧЕСТВО(*) КАК КолВо
ПОМЕСТИТЬ Т2
ИЗ
	ВТ КАК X
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ КАК Y
		ПО (X.КвадратН > 0)
			И (Y.КвадратН > 0)
			И (3 * X.КвадратН + Y.КвадратН <= &Граница)

СГРУППИРОВАТЬ ПО
	3 * X.КвадратН + Y.КвадратН

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(*) В (1, 3, 5, 7, 9)

ИНДЕКСИРОВАТЬ ПО
	Н
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	3 * X.КвадратН - Y.КвадратН КАК Н,
	КОЛИЧЕСТВО(*) КАК КолВо
ПОМЕСТИТЬ Т3
ИЗ
	ВТ КАК X
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ КАК Y
		ПО X.Н > Y.Н
			И (X.КвадратН > 0)
			И (Y.КвадратН > 0)
			И (3 * X.КвадратН - Y.КвадратН <= &Граница)

СГРУППИРОВАТЬ ПО
	3 * X.КвадратН - Y.КвадратН

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(*) В (1, 3, 5, 7, 9)

ИНДЕКСИРОВАТЬ ПО
	Н
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	4 * ВТ.Н + 1 КАК Кандидат,
	Т1.КолВо КАК КолВо
ПОМЕСТИТЬ мКандидаты
ИЗ
	ВТ КАК ВТ
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Т1 КАК Т1
		ПО (4 * ВТ.Н + 1 <= &Граница)
			И (4 * ВТ.Н + 1 = Т1.Н)

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	6 * ВТ.Н + 1,
	Т2.КолВо
ИЗ
	ВТ КАК ВТ
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Т2 КАК Т2
		ПО (6 * ВТ.Н + 1 <= &Граница)
			И (6 * ВТ.Н + 1 = Т2.Н)

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	12 * ВТ.Н - 1,
	Т3.КолВо
ИЗ
	ВТ КАК ВТ
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Т3 КАК Т3
		ПО (12 * ВТ.Н - 1 <= &Граница)
			И (12 * ВТ.Н - 1 = Т3.Н)

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	1,
	1

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	2,
	1

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	3,
	1
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	мКандидаты.Кандидат КАК НатуральноеЧисло
ПОМЕСТИТЬ мГруппировка
ИЗ
	мКандидаты КАК мКандидаты
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	ВЫБОР
		КОГДА ВТ.КвадратН = 0
			ТОГДА &Граница
		ИНАЧЕ ВТ.КвадратН
	КОНЕЦ КАК КвадратН,
	ВТ.Н КАК Н
ПОМЕСТИТЬ мДляПроверки
ИЗ
	мГруппировка КАК мГруппировка
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВТ КАК ВТ
		ПО мГруппировка.НатуральноеЧисло = ВТ.Н
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	мДляПроверки.Н
ПОМЕСТИТЬ мПростыеЧисла
ИЗ
	мДляПроверки КАК мДляПроверки
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ мДляПроверки КАК мДелители
		ПО (мДелители.КвадратН <= мДляПроверки.Н)
			И ((ВЫРАЗИТЬ(мДляПроверки.Н / мДелители.Н КАК ЧИСЛО(19, 0))) = мДляПроверки.Н / мДелители.Н)

СГРУППИРОВАТЬ ПО
	мДляПроверки.Н

ИМЕЮЩИЕ
	КОЛИЧЕСТВО(мДляПроверки.Н) = 1
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	КОЛИЧЕСТВО(мПростыеЧисла.Н) - 1 КАК НатуральноеЧисло
ИЗ
	мПростыеЧисла КАК мПростыеЧисла

Во всех приведенных запросах вычисляется количество простых чисел не превышающих заданную границу, это способ проверки правильности алгоритма. Найденные значения я сравниваю с результатами выполнения функции primepi на сайте http://www.wolframalpha.com.

Нам осталось сказать, где это можно использовать. Разумеется, ни в одной типовой конфигурации такие задачи не встречаются. Но подобный вопрос может встретиться на собеседовании при приеме на работу. Теперь вы знаете, как на него ответить.

Каталог решений - Как получить список простых чисел в запросе