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

21.03.19

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование		По подписке [?]	Купить один файл
Решето Эратосфена .epf 8,91Kb 8	8	Скачать (1 SM)	Купить за 1 850 руб.

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;
 КонецЕсли;
КонецЦикла;
Сообщить(Строка(Счетчик));

+8 –

См. также

Метод Дугласа-Пойкера

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

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

1 стартмани

30.01.2024 3927 stopa85 12

Алгоритм симплекс-метода

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

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

19.10.2023 8627 user1959478 52

Математический тренажер созданный для тестирования Вашего ребенка на предмет: умножения, деления, сложения и вычитания.

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

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023 3848 maksa2005 8

Регулярки на 1С

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

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

1 стартмани

09.06.2023 11601 8 SpaceOfMyHead 19

Мини-обзор разных решений задач

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

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023 5069 RustIG 9

Тестирование средств 1С для решения СЛАУ

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

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

23.11.2022 4218 gzharkoj 14

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

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

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

1 стартмани

21.03.2022 9182 7 kalyaka 11

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

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

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

16.12.2021 6372 fishca 12

Комментарии

Подписаться на ответы Инфостарт бот

Свернуть все

0. torg1c 36 02.08.12 18:26 Сейчас в теме

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.

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

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

1. Armando 1401 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 392 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);

Показать

6. torg1c 36 06.08.12 10:49 Сейчас в теме

(5) Nykyanen,

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

Я попробовал Эратосфена через Соответствия так оперативки не хватило.

7. Iaskeliainen 392 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 392 08.08.12 20:02 Сейчас в теме

(8) у меня 8 гиг, win 7 корп.
База серверная на MS SQL.
Думаю проблема в управляемых формах.

9. quebracho 22 08.08.12 12:05 Сейчас в теме

Баян?
http://infostart.ru/public/22292/

10. torg1c 36 08.08.12 15:43 Сейчас в теме

Невозможно не согласиться :)
Но я поиском не нашел, видимо потому, что только по 8.2 искал.

12. alean 35 09.08.12 09:22 Сейчас в теме

очень интересно. особенно в плане быстродействия клиен-сервер
в алгоритме Эратосфена Pow(i,2) вычисляется дважды.

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