Факторизация числа

18.11.13

Разработка - Математика и алгоритмы

Дается алгоритм разложения целого числа на простые множители с учетом их кратности (представление числа в виде произведения простых множителей). Вычисления проведены с помощью языка запросов 1С.

Представлен алгоритм решения задачи методом перебора возможных делителей.
Функция ProtoText для формирования порождающего запроса, генерирующего числовую последовательность, взята из статьи Порождающий запрос от ildarovich.
Обработка прилагается.

Процедура Факторизация()
	ПроверкаЧисло = 0;
	ТабРазложение.Очистить();
	
	Половина = Цел((ЗаданноеЧисло)/2)+1;
	
	МВТ = Новый МенеджерВременныхТаблиц;
	Запрос = Новый Запрос;
	Запрос.МенеджерВременныхТаблиц = МВТ;
	Запрос.УстановитьПараметр("П", ЗаданноеЧисло);	
	Запрос.Текст = ProtoText(Половина)+ 
	";
	|Выбрать X как м Поместить ПотенциальныеМножители0 ИЗ #r 
	|Где X <>1 И  (X = 2 или X = 3 или (X -1)/6 - ВЫРАЗИТЬ((X -1)/6 КАК ЧИСЛО(32, 0)) = 0 или (X +1)/6 - ВЫРАЗИТЬ((X +1)/6 КАК ЧИСЛО(32, 0)) = 0);
	|Выбрать 1 как ПростойМножитель, 1 как Кратность Поместить Результат;
	|Выбрать * ИЗ ПотенциальныеМножители0";
	Запрос.Текст = СтрЗаменить(Запрос.Текст, "#r", "r"+Формат(Половина, "ЧГ="));
	
	КоличествоПотенциальныхМножителей = Запрос.Выполнить().Выбрать().Количество();
	ш = 0;
	Накопление = 1;
	Остаток = ЗаданноеЧисло;
	Пока КоличествоПотенциальныхМножителей <> 0 Цикл
		
		Запрос.Текст = "Выбрать м Поместить ПотенциальныеМножители#Замена2_0 из ПотенциальныеМножители#Замена1 
		|Где &П/м - ВЫРАЗИТЬ(&П/м КАК ЧИСЛО(32, 0)) = 0; 
		|Выбрать м Поместить ПотенциальныеМножители#Замена2 Из ПотенциальныеМножители#Замена2_0  
		|Где Не м В(Выбрать П2.м Из ПотенциальныеМножители#Замена2_0 как П1 
		|				Внутреннее Соединение ПотенциальныеМножители#Замена2_0 Как П2 
		|			       По П2.м/П1.м<>1 и П2.м/П1.м - Выразить(П2.м/П1.м КАК ЧИСЛО(32, 0))=0);
		|Выбрать ПростойМножитель, Кратность  Поместить РезультатВрем ИЗ Результат; Уничтожить Результат;  
		|Выбрать ПростойМножитель, Кратность Поместить Результат ИЗ РезультатВрем 
		|Объединить Все 
		|Выбрать м, 1 Из ПотенциальныеМножители#Замена2; Уничтожить РезультатВрем;
		|Уничтожить ПотенциальныеМножители#Замена2_0;
		|Выбрать * ИЗ ПотенциальныеМножители#Замена2";
		
		Запрос.Текст = СтрЗаменить(Запрос.Текст, "#Замена1", Формат(ш, "ЧРГ=; ЧН=; ЧГ="));
		Запрос.Текст = СтрЗаменить(Запрос.Текст, "#Замена2", Формат(ш+1, "ЧРГ=; ЧГ="));
		
		ТабПроизведение = Запрос.Выполнить().Выгрузить();
		
		НовоеНакопление = 1;
		Для каждого Стр Из ТабПроизведение Цикл
			НовоеНакопление = НовоеНакопление*Стр.м;
		КонецЦикла;
		Накопление = Накопление*НовоеНакопление;
		КоличествоПотенциальныхМножителей = ТабПроизведение.Количество();
		ш = ш + 1;
		Остаток = Остаток/НовоеНакопление;
		Запрос.УстановитьПараметр("П", Остаток);
	КонецЦикла; 
	
	Если Накопление = 1 Тогда
		ПроверкаЧисло = ЗаданноеЧисло;
		Предупреждение("Простое число!", 2);
	Иначе
		Запрос.Текст = "Выбрать ПростойМножитель, Сумма(Кратность) как Кратность ИЗ Результат где ПростойМножитель <> 1 Сгруппировать по ПростойМножитель";
		ТабРазложение.Загрузить(Запрос.Выполнить().Выгрузить());
		ПроверкаЧисло = Накопление;
	КонецЕсли; 
КонецПроцедуры

факторизация простые числа простые множители произведение

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1756    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4427    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7466    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7856    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4448    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8846    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

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

31.08.2021    7813    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. nixel 1404 13.11.13 15:58 Сейчас в теме
Я пытаюсь вспомнить все отчеты с какой-либо сложной аналитикой или сложные алгоритмы, вроде автоматического формирования расписания, но не могу представить, где может пригодится факторизация числа.

За алгоритм - определенно плюс, люблю математику в 1с.
Просто любопытно, для каких задач это писалось?
2. zaxarovsky 111 13.11.13 16:15 Сейчас в теме
(1) nixel, спасибо за + :)
эта вещь понадобилась мне для более крупной задачи, которая, однако, тоже математического толка, нежели прикладного в смысле применимости для реляционных БД.
Статья выйдет здесь же несколько позднее, там и будут даны комментарии.
3. nixel 1404 13.11.13 16:28 Сейчас в теме
(2) хорошо, жду статью, заинтересовали :)
4. DAnry 8 13.11.13 21:55 Сейчас в теме
Такие вещи, конечно, не на каждый день. Но может пригодиться. За работу плюс
5. Makushimo 160 18.11.13 07:23 Сейчас в теме
мнээ
это, наверное, круто очень.
Но почему все в виде XML разметки написано?
Текст воспринимается как каша.
6. zaxarovsky 111 18.11.13 07:57 Сейчас в теме
(5) Makushimo, хм, это проблемка движка Инфостарта. Задал вопрос техподдержке, подождем ответа.
Иногда отображается нормально.
7. Makushimo 160 18.11.13 08:33 Сейчас в теме
Оставьте свое сообщение