Быстрая проверка натурального числа на простоту

@Thinker · Регистрация: 26.08.2011

Студворк — интернет-сервис помощи студентам

Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}$ , то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм

C++

int Prime(unsigned long a)
{
   unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}

В данном алгоритме из множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}$ отброшено 50% четных чисел, так как если число a не делится на 2, то нет смыла делить его на 4, 6 и т.д. Данный метод можно усовершенствовать и отбросить из множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}$ больше чисел. Для этого выбирается некоторое число m, равное произведению простых чисел без степеней и рассматриваются только те элементы множества $https://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}$ , которые взаимно просты с m. Например, если m = 6 = 2*3, то из этого множества отбрасывается 66% элементов (ненужных проверок). В этом случае алгоритм будет быстрее предыдущего при больших n

C++

int Prime(unsigned long a)
{
   unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}

Если m = 30 = 2*3*5, то такой алгоритм будет еще быстрее и отбрасывает уже 74% лишних элементов

C++

int Prime(unsigned long a)
{
   unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 || a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
      return 0;
   bound = sqrt((double)a);
   i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
   while (i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
   {
       i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
   }
   if (i8 <= bound ||
      i1 <= bound && a % i1 == 0 ||
      i2 <= bound && a % i2 == 0 ||
      i3 <= bound && a % i3 == 0 ||
      i4 <= bound && a % i4 == 0 ||
      i5 <= bound && a % i5 == 0 ||
      i6 <= bound && a % i6 == 0 ||
      i7 <= bound && a % i7 == 0)
         return 0;
   return 1;
}

Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.

@Jin X · 04.03.2019, 17:41

Сообщение от Catstail

Создать упорядоченный массив всех простых чисел от 2 до 9973, а проверяемое число искать двоичным поиском в этом массиве... Проверяться будет "пулей" !

Во-первых, это слишком медленно.
Во-вторых, зачем использовать 1129*2 = 2258 байт памяти, когда можно 10000/8/2 = 625 ?

Для этого нужно создать битовый набор, в котором отмечать простые числа как 1, составные - как 0. Разумеется, только для нечётных чисел.

А вообще, по теме welcome сюда: https://www.cyberforum.ru/blog... g5712.html

Финальный код (он же тут в последнем спойлере) похож на тот, что в шапке этого топика (работает с той же скоростью).

Есть ещё такой вариант (наиболее быстрый из более или менее адекватных; на 25% быстрее выложенного в статье или того, что в шапке этого топика):

C++

#include <iostream>
#include <cmath>
#include <ctime>
 
using std::cout;
 
// Тест простоты числа n
bool is_prime(unsigned long n)
{
  // Проверяем, что число больше 1, а также частные случаи простых чисел (2, 3, 5, 7 и 11)
  if (n <= 12) {
    return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11);
  }
  // Проверяем делимость на 2, 3, 5, 7 и 11
  // p.s. При оптимизации нормальными компиляторами с опцией -O2 деление (взятие остатка от деления)
  // на константу будет выполняться быстрее, чем на переменную с заранее неизвестным значением
  if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0) { return false; }
 
  // Проверяем делимость на остальные числа, не делящиеся на 2, 3, 5, 7 и 11, начиная с 13
  // (с приращением, взятым из массива delta): 11, 13, 17, 19, 23, 29, 31, 37, 41, 43...
  static const unsigned char delta[480] = {
    4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4,
    14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6,
    2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6,
    2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4,
    12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2,
    4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4,
    2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4,
    2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8,
    4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2,
    10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2,
    4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2,
    4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4,
    8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2,
    10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2,
    6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6,
    2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4,
    8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
    10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2,
    4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4,
    2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12 };  // массив приращений
  for (unsigned long div = 13, idx = 0, max_div = sqrt(n);  // idx - индекс в массиве delta
    div <= max_div;
    div += delta[idx], idx = (idx == 479 ? 0 : idx + 1)) {  // увеличиваем индекс с остатком от деления на 480
    if (n % div == 0) { return false; }
  }
 
  // Число простое
  return true;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
// Класс для замера времени выполнения кода
class TimeMeasure
{
  clock_t _start_time;
public:
  // Запустить таймер
  void start()
  {
    _start_time = clock();
  }
  // Остановить таймер и вывести время
  void stop_and_show()
  {
    double time = clock() - _start_time;
    time /= CLOCKS_PER_SEC;
    cout << "[Elapsed time: " << time << " seconds]" << "\n";
  }
};
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main()
{
  // Вывод простых чисел до 1'000 (тест Миллера)
  for (unsigned long n = 0; n < 1'000; ++n) {
    if (is_prime(n)) {
      cout << n << " ";
    }
  }
  cout << "\n\n";
 
  // Замер производительности
  TimeMeasure tm;
  tm.start();
  int count = 0;
  for (unsigned long n = 0; n <= 10'000'000; ++n) {
    if (is_prime(n)) { ++count; }
  }
  tm.stop_and_show();
  cout << "count = " << count << "\n";
 
  return 0;
}

Вариант проще

C++

#include <iostream>
#include <cmath>
#include <ctime>
 
using std::cout;
 
// Тест простоты числа n
bool is_prime(unsigned long n)
{
  // Проверяем, что число больше 1, а также частные случаи простых чисел (2, 3, 5 и 7)
  if (n <= 10) {
    return (n == 2 || n == 3 || n == 5 || n == 7);
  }
  // Проверяем делимость на 2, 3, 5 и 7
  // p.s. При оптимизации нормальными компиляторами с опцией -O2 деление (взятие остатка от деления)
  // на константу будет выполняться быстрее, чем на переменную с заранее неизвестным значением
  if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) { return false; }
 
  // Проверяем делимость на остальные числа, не делящиеся на 2, 3, 5 и 7, начиная с 11
  // (с приращением, взятым из массива delta): 11, 13, 17, 19, 23, 29, 31, 37, 41, 43...
  static const unsigned char delta[48] = {
    2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2,
    4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10 };  // массив приращений
  for (unsigned long div = 11, idx = -1, max_div = sqrt(n);  // idx - индекс в массиве delta
    div <= max_div;
    div += delta[idx], idx = (idx == 47 ? 0 : idx + 1)) {  // увеличиваем индекс с остатком от деления на 48
    if (n % div == 0) { return false; }
  }
 
  // Число простое
  return true;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
// Класс для замера времени выполнения кода
class TimeMeasure
{
  clock_t _start_time;
public:
  // Запустить таймер
  void start()
  {
    _start_time = clock();
  }
  // Остановить таймер и вывести время
  void stop_and_show()
  {
    double time = clock() - _start_time;
    time /= CLOCKS_PER_SEC;
    cout << "[Elapsed time: " << time << " seconds]" << "\n";
  }
};
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main()
{
  // Вывод простых чисел до 1'000 (тест Миллера)
  for (unsigned long n = 0; n < 1'000; ++n) {
    if (is_prime(n)) {
      cout << n << " ";
    }
  }
  cout << "\n\n";
 
  // Замер производительности
  TimeMeasure tm;
  tm.start();
  int count = 0;
  for (unsigned long n = 0; n <= 10'000'000; ++n) {
    if (is_prime(n)) { ++count; }
  }
  tm.stop_and_show();
  cout << "count = " << count << "\n";
 
  return 0;
}

Ещё проще (примерно как в шапке этого топика, скорость та же)

C++

#include <iostream>
#include <cmath>
#include <ctime>
 
using std::cout;
 
// Тест простоты числа n
bool is_prime(unsigned long n)
{
  // Проверяем, что число больше 1, а также частные случаи простых чисел (2, 3 и 5)
  if (n <= 5) {
    return (n >= 2 && n != 4);
  }
  // Проверяем делимость на 2, 3 и 5
  // p.s. При оптимизации нормальными компиляторами с опцией -O2 деление (взятие остатка от деления)
  // на константу будет выполняться быстрее, чем на переменную с заранее неизвестным значением
  if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0) { return false; }
 
  // Проверяем делимость на остальные числа, не делящиеся на 2, 3 и 5, начиная с 7
  // (с приращением, взятым из массива delta): 7, 11, 13, 17, 19, 23, 29, 31, 37...
  static const unsigned char delta[8] = { 4, 2, 4, 2, 4, 6, 2, 6 };  // массив приращений
  for (unsigned long div = 7, idx = 0, max_div = sqrt(n);  // idx - индекс в массиве delta
    div <= max_div;
    div += delta[idx], idx = idx+1 & 7) {  // увеличиваем индекс на 1 с остатком от деления на 8
    if (n % div == 0) { return false; }
  }
 
  // Число простое
  return true;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
// Класс для замера времени выполнения кода
class TimeMeasure
{
  clock_t _start_time;
public:
  // Запустить таймер
  void start()
  {
    _start_time = clock();
  }
  // Остановить таймер и вывести время
  void stop_and_show()
  {
    double time = clock() - _start_time;
    time /= CLOCKS_PER_SEC;
    cout << "[Elapsed time: " << time << " seconds]" << "\n";
  }
};
 
////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main()
{
  // Вывод простых чисел до 1'000 (тест Миллера)
  for (unsigned long n = 0; n < 1'000; ++n) {
    if (is_prime(n)) {
      cout << n << " ";
    }
  }
  cout << "\n\n";
 
  // Замер производительности
  TimeMeasure tm;
  tm.start();
  int count = 0;
  for (unsigned long n = 0; n <= 10'000'000; ++n) {
    if (is_prime(n)) { ++count; }
  }
  tm.stop_and_show();
  cout << "count = " << count << "\n";
 
  return 0;
}

Байт · 04.03.2019, 17:47

Сообщение от Jin X

когда можно 10000/8/2 =

Можно даже 10000/30

@Jin X · 04.03.2019, 17:49

Сообщение от Байт

Можно даже 10000/30

Можно, но геморно сопоставлять число индексу.
Хотя, может, и не слишком геморно, я пока даже не пытался этого делать...

@Catstail · 04.03.2019, 18:03

Сообщение от Jin X

Во-первых, это слишком медленно.
Во-вторых, зачем использовать 1129*2 = 2258 байт памяти, когда можно 10000/8/2 = 625 ?
Для этого нужно создать битовый набор, в котором отмечать простые числа как 1, составные - как 0. Разумеется, только для нечётных чисел.

- не думаю, что здесь так важна копеечная экономия памяти. А "слишком медленно" - по сравнению с чем?

@Jin X · 04.03.2019, 19:07

Сообщение от Catstail

не думаю, что здесь так важна копеечная экономия памяти

Задумаетесь, когда кол-во чисел пойдёт на десятки и сотни миллионов

Сообщение от Catstail

А "слишком медленно" - по сравнению с чем?

По сравнению с бинарным поиском.

@Catstail · 04.03.2019, 19:14

Сообщение от Jin X

Задумаетесь, когда кол-во чисел пойдёт на десятки и сотни миллионов

- так я-то писал (в 2012-м) о числах до 10 тыс...

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

@Jin X · 04.03.2019, 19:39

Сообщение от Catstail

так я-то писал (в 2012-м) о числах до 10 тыс...

Да, я понял. Просто сейчас нужно 10 тыс, а завтра понадобится 10 млн. Зачем заново переписывать функцию, когда можно сразу сделать оптимально и на все случаи жизни, что называется?

Байт · 04.03.2019, 23:40

Сообщение от Jin X

Просто сейчас нужно 10 тыс, а завтра понадобится 10 млн

Все это копеечки, уважаемый. Реально задачу нахождения простых чисел интересуют штуки порядка 10^10¹⁰. Или больше. И тут даже есть возможность весьма приличную денежку заработать. А эти улучшения на 2 процента... Ну, как развлечения досужего ума, это все неплохо...

Добавлено через 30 минут
Jin X, вы лучше на решето Аткина посмотрите. Я, по правде, в нем так и не разобрался. Но говорят, оно дает выигрыш на порядок. И математика там симпатичная, не шибко заумная...

@Вадим Тукаев · 05.03.2019, 07:25

Если нужно проверять на простоту числа до 10000, то проще всего тупо их все во множество положить.

А учитывая объем памяти современных компьютеров, такой трюк и с 10000000 прокатит. Я недавно видел простенькое приложеньице, про которые в 90-х говорили "и эта фитюлька после компиляции в Дельфи 400 Кбайт весит??? Не, я лучше на С++ перепишу" весом... более 400 Мегабайт. И ее даже пытаются продавать за небольшую денежку. И ведь кто-то наверняка покупает...

@Jin X · 05.03.2019, 15:46

Сообщение от Байт

Jin X, вы лучше на решето Аткина посмотрите.

Это в планах.
Кстати, интересует вопрос. Что быстрее: решето Аткина или Эратосфена?

Добавлено через 1 минуту

Сообщение от Jin X

11, 13, 17, 19, 23, 29, 31, 37, 41, 43...

Опечатка, 11 тут не будет

И лучше всё же unsigned int, чем unsigned long (иначе на Linux 64 тормозить будет).

Байт · 05.03.2019, 19:42

Сообщение от Jin X

Что быстрее: решето Аткина или Эратосфена?

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

Сообщение от Jin X

лучше всё же unsigned int, чем unsigned long

Все блох ловите? Ну-ну...

@Jin X · 05.03.2019, 20:40

Сообщение от Байт

Все блох ловите? Ну-ну...

Уверены?
На Linux 64 long имеет размер 8 байт, а не 4, как на винде.
Уж не знаю, почему такая разница в скорости (раз система 64-битная), но к примеру, на tio.run разница в 2 раза: unsigned int и unsigned long

@alexu_007 · 28.05.2020, 22:35

Сообщение от Thinker

Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.

Нехилый алгоритм, хоть и непонятный. Работает в 2.3 раза быстрее, чем простым делением.

Байт · 12.06.2020, 10:54

Вот такой код, решающий немного другую задачу. А именно, Найти K-е простое число. По ходу находятся все первые K простых чисел

C++

vector<int>primes;
primes.reserve(K);  // Чтоб не было лишних перераспределений памяти...
for(i=2; primes.size() < K; i++) {
  bool isP = true;
  for(j=0; j< primes.size(); j++) {
    int p = primes[j];
    if (p*p > i) break;
    if (i%p) == 0) {
     isP = false;
     break;
   }
  }
   if (isP) primes.push_back(i);
}
cout << primes[primes.size() - 1);

Тут проверяется делимость только на простые, то есть выбрасываются из проверки не только 2, 3, 5, но и все простые вообще.
Конечно, для определения простоты конкретного числа, этот подход не быстр. Его модификации можно предложить, когда требуется определить простоту множества чисел. С расширением вектора primes и двоичным поиском.
Но вот эффективно применить его к анализу конкретного числа не получается...

Байт Диссидент 27697 / 17314 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	04.03.2019, 17:47	102
	Сообщение от Jin X когда можно 10000/8/2 = Можно даже 10000/30 0

@Jin X Asm♥/C++/Delphi/Py/PHP/Go 6336 / 1943 / 219 Регистрация: 14.12.2014 Сообщений: 4,049 Записей в блоге: 12
	04.03.2019, 17:49	103
	Сообщение от Байт Можно даже 10000/30 Можно, но геморно сопоставлять число индексу. Хотя, может, и не слишком геморно, я пока даже не пытался этого делать... 0

@Catstail Модератор 35623 / 20008 / 4186 Регистрация: 12.02.2012 Сообщений: 33,184 Записей в блоге: 13
	04.03.2019, 18:03	104
	Сообщение от Jin X Во-первых, это слишком медленно. Во-вторых, зачем использовать 1129*2 = 2258 байт памяти, когда можно 10000/8/2 = 625 ? Для этого нужно создать битовый набор, в котором отмечать простые числа как 1, составные - как 0. Разумеется, только для нечётных чисел. - не думаю, что здесь так важна копеечная экономия памяти. А "слишком медленно" - по сравнению с чем? 0

@Jin X Asm♥/C++/Delphi/Py/PHP/Go 6336 / 1943 / 219 Регистрация: 14.12.2014 Сообщений: 4,049 Записей в блоге: 12
	04.03.2019, 19:07	105
	Сообщение от Catstail не думаю, что здесь так важна копеечная экономия памяти Задумаетесь, когда кол-во чисел пойдёт на десятки и сотни миллионов Сообщение от Catstail А "слишком медленно" - по сравнению с чем? По сравнению с бинарным поиском. 0

@Catstail Модератор 35623 / 20008 / 4186 Регистрация: 12.02.2012 Сообщений: 33,184 Записей в блоге: 13
	04.03.2019, 19:14	106
	Сообщение от Jin X Задумаетесь, когда кол-во чисел пойдёт на десятки и сотни миллионов - так я-то писал (в 2012-м) о числах до 10 тыс... Да, если использовать битовый массив, то будет быстрее двоичного поиска. Согласен. Правда Ваша. 0

@Jin X Asm♥/C++/Delphi/Py/PHP/Go 6336 / 1943 / 219 Регистрация: 14.12.2014 Сообщений: 4,049 Записей в блоге: 12
	04.03.2019, 19:39	107
	Сообщение от Catstail так я-то писал (в 2012-м) о числах до 10 тыс... Да, я понял. Просто сейчас нужно 10 тыс, а завтра понадобится 10 млн. Зачем заново переписывать функцию, когда можно сразу сделать оптимально и на все случаи жизни, что называется? 0

Байт Диссидент 27697 / 17314 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	04.03.2019, 23:40	108
	Сообщение от Jin X Просто сейчас нужно 10 тыс, а завтра понадобится 10 млн Все это копеечки, уважаемый. Реально задачу нахождения простых чисел интересуют штуки порядка 10^10¹⁰. Или больше. И тут даже есть возможность весьма приличную денежку заработать. А эти улучшения на 2 процента... Ну, как развлечения досужего ума, это все неплохо... Добавлено через 30 минут Jin X, вы лучше на решето Аткина посмотрите. Я, по правде, в нем так и не разобрался. Но говорят, оно дает выигрыш на порядок. И математика там симпатичная, не шибко заумная... 0

@Вадим Тукаев 307 / 288 / 116 Регистрация: 23.01.2018 Сообщений: 933
	05.03.2019, 07:25	109
	Если нужно проверять на простоту числа до 10000, то проще всего тупо их все во множество положить. А учитывая объем памяти современных компьютеров, такой трюк и с 10000000 прокатит. Я недавно видел простенькое приложеньице, про которые в 90-х говорили "и эта фитюлька после компиляции в Дельфи 400 Кбайт весит??? Не, я лучше на С++ перепишу" весом... более 400 Мегабайт. И ее даже пытаются продавать за небольшую денежку. И ведь кто-то наверняка покупает... 0

@Jin X Asm♥/C++/Delphi/Py/PHP/Go 6336 / 1943 / 219 Регистрация: 14.12.2014 Сообщений: 4,049 Записей в блоге: 12
	05.03.2019, 15:46	110
	Сообщение от Байт Jin X, вы лучше на решето Аткина посмотрите. Это в планах. Кстати, интересует вопрос. Что быстрее: решето Аткина или Эратосфена? Добавлено через 1 минуту Сообщение от Jin X 11, 13, 17, 19, 23, 29, 31, 37, 41, 43... Опечатка, 11 тут не будет И лучше всё же `unsigned int`, чем `unsigned long` (иначе на Linux 64 тормозить будет). 0

Байт Диссидент 27697 / 17314 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	05.03.2019, 19:42	111
	Сообщение от Jin X Что быстрее: решето Аткина или Эратосфена? Народ говорит, что Аткин пошустрее будет Сообщение от Jin X лучше всё же unsigned int, чем unsigned long Все блох ловите? Ну-ну... 0

@Jin X Asm♥/C++/Delphi/Py/PHP/Go 6336 / 1943 / 219 Регистрация: 14.12.2014 Сообщений: 4,049 Записей в блоге: 12
	05.03.2019, 20:40	112
	Сообщение от Байт Все блох ловите? Ну-ну... Уверены? На Linux 64 long имеет размер 8 байт, а не 4, как на винде. Уж не знаю, почему такая разница в скорости (раз система 64-битная), но к примеру, на tio.run разница в 2 раза: unsigned int и unsigned long 0

@alexu_007 609 / 623 / 98 Регистрация: 29.05.2015 Сообщений: 3,841
	28.05.2020, 22:35	113
	Сообщение от Thinker Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте. Нехилый алгоритм, хоть и непонятный. Работает в 2.3 раза быстрее, чем простым делением. 0

	12.06.2020, 10:54