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

Программирование - Теория программирования

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

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

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

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

	Наименование	Файл	Версия	Размер
	Решето Эратосфена .epf 8,91Kb 02.08.12 7	.epf		8,91Kb	7	Скачать

См. также

Агрегатное суммирование строк в запросе – сложно, но не невозможно

Определение кратчайших путей, критических путей одним запросом

Полная методичка к курсу "Программирование 8.2"

Разработка синтаксического анализатора языка запросов на языке 1С

Еще один взгляд на проблему «жизнь без последовательностей». Часть вторая (практическая)

Включаем звук в 1С. Доступно и всерьез.

Демо связи веб сервисов 1С и php

Дао программирования

Конспект лекций по курсу «Автоматизированные информационные системы»

Автоформатирование кода

Технология создания коммерческих разработок на базе Базовой конфигурации "Управление Торговлей, ред.10.3"

Модуль менеджера или статические методы класса?

Пророк в своем отечестве или Читаем XML с помощью XDTO

Создание внешних печатных форм для 1С 8.1 на основе типовых. (Через подмену контекста).

Объектно-ориентированный взгляд на программирование в 1С

Теория поиска ошибок :)

Еще один способ расчета остатков на каждый день в запросе

Как я победил блокировки (deadlock)

Парсинг сайта без использования встроенного браузера для начинающих

Анализ цикломатической сложности кода

Комментарии

Сохранить

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

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

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

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

1. Armando Armando (Armando) 1381 02.08.12 21:56 Сейчас в теме

Прикладной смысл есть?

2. Лев Лукашов (Skimen) 225 03.08.12 02:05 Сейчас в теме

(1)Например, сравнение производительности обработки данных в памяти для разных билдов платформы.

3. Василий Антонов (khaoos) 239 03.08.12 04:55 Сейчас в теме

Сравнивать версии платформ на скорость вполне интересно таким образом. С каждым новым релизом запускать обработку и надеяться на чудо :)

4. Алексей Роза (DoctorRoza) 03.08.12 09:25 Сейчас в теме

Всегда плюсую за подобные полеты фантазии и повышения личной образованности! :)

5. Матти Нюкянен (Nykyanen) 215 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 (torg1c) 36 06.08.12 10:49 Сейчас в теме

(5) Nykyanen,

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

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

7. Матти Нюкянен (Nykyanen) 215 06.08.12 12:58 Сейчас в теме

(6) torg1c, у меня на 8.3.1 и 8.2.16 и 8.2.15.319 в управляемых формах ваш алгоритм на 100 000 000 выдавал ошибку переполнения при создании массива, и платформа уходит в краш.
При подходе, который предложил я, требуется в 3 раза меньше размер массива

8. torg1c (torg1c) 36 06.08.12 14:03 Сейчас в теме

Видимо памяти мало, у меня 6 Гиов 64 win 2008 крэша не было.

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

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

Но бесспорно, что алгоритм Аткина по всем параметрам лучше!

9. qwe qwerty (quebracho) 23 08.08.12 12:05 Сейчас в теме

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

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

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

11. Матти Нюкянен (Nykyanen) 215 08.08.12 20:02 Сейчас в теме

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

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

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

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