Решето Аткина быстрее.
Вот пример упрощенного варианта.
Работает в 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);
Показать
