Решето Эратосфена

21.03.19

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

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому. Нашел тест http://easy-coding.blogspot.com/2010/03/go-c-c.html и думаю дай проверю каково это будет в 1С.

Скачать файлы

Наименование Файл Версия Размер
Решето Эратосфена
.epf 8,91Kb
8
.epf 8,91Kb 8 Скачать
n = ЭлементыФормы.ПредельноеЧисло.Значение;	
A = Новый Массив(n+1);
Для Индекс = 0 По A.ВГраница() Цикл
	A[Индекс] = Истина;
КонецЦикла;
Сообщить(Строка(ТекущаяДата()));
Для i = 2 По n Цикл
	Если Pow(i,2)>n Тогда
		Прервать;
 КонецЕсли;
 Если A[i] Тогда
		j = Pow(i,2);
 Пока j<=n Цикл
	 Если A[j] Тогда
				A[j]=Ложь;
 КонецЕсли;
			j = j + i; 
 КонецЦикла;
 КонецЕсли;
КонецЦикла;
Сообщить(Строка(ТекущаяДата()));
Счетчик = 0;
Стр = "";
Для i = 2 По n Цикл
	Если A[i] Тогда
		Счетчик = Счетчик + 1;
 КонецЕсли;
КонецЦикла;
Сообщить(Строка(Счетчик)); 

См. также

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

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

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

1 стартмани

30.01.2024    1753    stopa85    12    

33

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

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

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

19.10.2023    4415    user1959478    50    

34

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

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

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

1 стартмани

09.06.2023    7455    4    SpaceOfMyHead    17    

56

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

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

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

1 стартмани

21.03.2022    7854    7    kalyaka    11    

44

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

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

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

16.12.2021    4444    fishca    13    

36

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

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

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

12.10.2021    8832    John_d    73    

46

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

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

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

31.08.2021    7797    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
0. torg1c 36 02.08.12 18:26 Сейчас в теме
Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.

Нашел тест http://easy-coding.blogspot.com/2010/03/go-c-c.html и думаю дай проверю каково это будет в 1С.

Перейти к публикации

1. Armando 1399 02.08.12 21:56 Сейчас в теме
Прикладной смысл есть?
2. Skimen 246 03.08.12 02:05 Сейчас в теме
(1)Например, сравнение производительности обработки данных в памяти для разных билдов платформы.
3. khaoos 239 03.08.12 04:55 Сейчас в теме
Сравнивать версии платформ на скорость вполне интересно таким образом. С каждым новым релизом запускать обработку и надеяться на чудо :)
4. DoctorRoza 03.08.12 09:25 Сейчас в теме
Всегда плюсую за подобные полеты фантазии и повышения личной образованности! :)
5. Iaskeliainen 384 03.08.12 22:58 Сейчас в теме
Решето Аткина быстрее.
Вот пример упрощенного варианта.
Работает в 3-4 раза быстрее.

Думаю если пошаманить можно ускорить еще в 3-4 раза.
	n = Число;	
	n6 = Окр(n / 6 + 0.49999999999,0,РежимОкругления.Окр15как20);
	n3 = n6 * 2;
	A = Новый Массив(n3 + 1);
	
	Для Индекс = 1 По n3 Цикл	
		A[Индекс] = Истина;
	КонецЦикла;
	
	дата2 = ТекущаяДата();
	Корень_n6 = Окр(Sqrt(n) / 6 - 0.499, 0, РежимОкругления.Окр15как10);
	
	Для m = 1 По Корень_n6 Цикл
		Если A[m * 2 - 1] Тогда		
			h1 = m * 4 - 1;	h2 = m * 8 - 1;
			h = h1;
			j = m * (6 * m - 2) * 2; 
			Пока j<=n3 Цикл	 
				Если A[j] Тогда A[j]=Ложь КонецЕсли;	
				j = j + h;  
				Если h = h1 Тогда h = h2 Иначе h = h1 КонецЕсли;
			КонецЦикла; 
		КонецЕсли;
		
		Если A[m * 2] Тогда		
			h3 = m * 4 + 1;	h4 = m * 8 + 1;
			h = h4;
			j = m * (6 * m + 2) * 2; 
			Пока j<=n3 Цикл	 
				Если A[j] Тогда A[j]=Ложь КонецЕсли;	
				j = j + h;  
				Если h = h3 Тогда h = h4 Иначе h = h3 КонецЕсли;
			КонецЦикла; 
		КонецЕсли;
	КонецЦикла;
	
	дата3 = ТекущаяДата();
	Счетчик = 2; // добавить простые 2, 3
	nn = (n / 6) * 2 - 1;
	
	Для i = 1 По nn Цикл	
		Если A[i] Тогда Счетчик = Счетчик + 1 КонецЕсли;
	КонецЦикла;
	
	доп = ?(i % 2 = 0, i * 3 + 1, (i + 1) * 3 - 1);
	Если доп <= n Тогда Счетчик = Счетчик + 1 КонецЕсли;
	
	Сообщить(Строка(Счетчик)); 	
	Сообщить(дата3 - дата2);
Показать
artmicro; alean; +2 Ответить
6. torg1c 36 06.08.12 10:49 Сейчас в теме
(5) Nykyanen,

Аткину зачет! Алгоритм очень быстрый и памяти меньше требуется.

Я попробовал Эратосфена через Соответствия так оперативки не хватило.
7. Iaskeliainen 384 06.08.12 12:58 Сейчас в теме
(6) у меня на 8.3.1 и 8.2.16 и 8.2.15.319 в управляемых формах ваш алгоритм на 100 000 000 выдавал ошибку переполнения при создании массива, и платформа уходит в краш.
При подходе, который предложил я, требуется в 3 раза меньше размер массива
8. torg1c 36 06.08.12 14:03 Сейчас в теме
Видимо памяти мало, у меня 6 Гиов 64 win 2008 крэша не было.

Вот табличка:



А вот соответствию памяти нужно еще больше, 1С закрывалась с сообщением "Недостаточно памяти".

Но бесспорно, что алгоритм Аткина по всем параметрам лучше!
11. Iaskeliainen 384 08.08.12 20:02 Сейчас в теме
(8) у меня 8 гиг, win 7 корп.
База серверная на MS SQL.
Думаю проблема в управляемых формах.
9. quebracho 22 08.08.12 12:05 Сейчас в теме
10. torg1c 36 08.08.12 15:43 Сейчас в теме
Невозможно не согласиться :)
Но я поиском не нашел, видимо потому, что только по 8.2 искал.
12. alean 35 09.08.12 09:22 Сейчас в теме
очень интересно. особенно в плане быстродействия клиен-сервер
в алгоритме Эратосфена Pow(i,2) вычисляется дважды.

Сообщить(""+ Строка(дата2-дата1) + " сек. / " + Счетчик + " чисел")
Оставьте свое сообщение