Что может быть проще простых чисел ? По определению, целое число называется простым, если оно не может быть представлено, как произведение двух меньших чисел. Единственное четное простое число - 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.
Нам осталось сказать, где это можно использовать. Разумеется, ни в одной типовой конфигурации такие задачи не встречаются. Но подобный вопрос может встретиться на собеседовании при приеме на работу. Теперь вы знаете, как на него ответить.
