gifts2017

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

Опубликовал torg1c (torg1c) в раздел Программирование - Теория программирования

Решето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 Скачать

См. также

Подписаться Добавить вознаграждение

Комментарии

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

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


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

1. Armando Armando (Armando) 02.08.12 21:56
2. Лев Лукашов (Skimen) 03.08.12 02:05
(1)Например, сравнение производительности обработки данных в памяти для разных билдов платформы.
3. Василий Антонов (khaoos) 03.08.12 04:55
Сравнивать версии платформ на скорость вполне интересно таким образом. С каждым новым релизом запускать обработку и надеяться на чудо :)
4. Алексей Роза (DoctorRoza) 03.08.12 09:25
Всегда плюсую за подобные полеты фантазии и повышения личной образованности! :)
5. Матти Нюкянен (Nykyanen) 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 Ответить 1
6. torg1c (torg1c) 06.08.12 10:49
(5) Nykyanen,

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

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

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



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

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

Сообщить(""+ Строка(дата2-дата1) + " сек. / " + Счетчик + " чисел")
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа