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

13 Comments

1. torg1c 02.08.2012 at 18:26

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

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

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

   Reply ↓
2. Armando 02.08.2012 at 21:56

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

   Reply ↓
3. Skimen 03.08.2012 at 02:05

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

   Reply ↓
4. khaoos 03.08.2012 at 04:55

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

   Reply ↓
5. DoctorRoza 03.08.2012 at 09:25

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

   Reply ↓
6. Nykyanen 03.08.2012 at 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);
   

   Показать

   Reply ↓
7. torg1c 06.08.2012 at 10:49

   (5) Nykyanen,

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

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

   Reply ↓
8. Nykyanen 06.08.2012 at 12:58

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

   Reply ↓
9. torg1c 06.08.2012 at 14:03

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

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

   

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

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

   Reply ↓
10. quebracho 08.08.2012 at 12:05

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

    Reply ↓
11. torg1c 08.08.2012 at 15:43

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

    Reply ↓
12. Nykyanen 08.08.2012 at 20:02

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

    Reply ↓
13. alean 09.08.2012 at 09:22

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

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

    Reply ↓