Алгоритмы → Поиск простых чисел


Так как я люблю решать различные математические задачки (projecteuler.net, diofant.ru, ...), постоянно необходимо делать одни и те же действия. Поэтому я создал блог «Алгоритмы», в котором буду периодически писать функции для решения различных задач. Думаю, многим будет полезно.
Желающие также могут поделиться своими наработками. Ссылки на другие ресурсы бросать не нужно, кто захочет, сам найдет через поисковые системы. Я любитель С++, поэтому весь синтаксис будет на нем.

Простое число — это число, которое делится без остатка только на единицу и само на себя.
Первая функция проверяет, простое ли число. Для этого нужно вызвать функцию, передав в нее число, которое нам нужно проверить на простоту.
int PrimeNumber(int number)
{
  for (int i=2; i<number; i++)
  {
    if (number%i == 0)
    {
      return 0;
    }

    if ((i==number) || (i>sqrt(number)))
    {
      return 1;
    }
  }

  return 1;
}

Вторая функция находит следующее простое число после числа, которое мы передаем в аргументах функции.
int NextPrimeNumber(int previous)
{
  int temp = previous + 1;
  int next = 0;
  int exit = 0;
  int i = 2;

  while (exit == 0)
  {
    if (temp%i == 0 && i!=temp)
    {
      temp++;
      i=2;
      continue;
    }

    if ((i==temp) || (i>sqrt(temp)))
    {
      next = temp;
      exit = 1;
    }

    i++;
  }

  return next;
}

Важно! В обеих функциях мы проверяем на остаток при делении нужного нам числа от двойки (так как на единицу оно и так будет делиться без остатка) до корня нашего числа. Это важная оптимизация нашего кода, которая позволяет работать нам с большими числами. Без нее поиск значения может значительно замедлиться.
  • +9
  • eReS
  • 02 января 2011, 16:42

Комментарии (15)

а если в машинные коды переписать алгоритм? ) И было бы интересно измерить, насколько увеличится производительность.
а если в машинные коды переписать алгоритм? )
Поломается переносимость и кроссплатформенность кода.
Ну это же не ява. Я как раз и говорил о том, что бы написать код под конкретный процессор дабы добиться максимально возможной производительности. Алгоритм простой можно и под разные системы команд переписать, не убудет.
За производительность напишу в завтрашней статьи :)
Спасибо, полезное дело делаете.
Впринципе можно еще вести список простых чисел и делимость проверять по ним. Так как если число не делится ни на одно простое число, то оно так же является простым.
Это особенно ускорит алгоритм при больших числах т.к. будут пропускаться все большие массивы чисел
Знаю это свойство :)
Ну пока незнаю как реализовать кратко и ясно. В будущем, надеюсь, исправлю это
Ну к примеру завести список, в который записывать все найденные простые числа. А условие цикла заменить на:
for (int i=2; i<List.Length; i++)
  {
    if (number%List[i] == 0)
    {
{
      return 0;
    }

    if ((i==number) || (i>sqrt(number)))
    {
      return 1;
    }
  }

Синтаксис правда больше на C# похож, но суть вроде передает. List это список, и осталось только вставить добавление очередного простого числа. Это уже по вкусу или перед return или уже при использовании функций
Поэкспериментирую, посмотрим насколько это себя оправдывает :)
По моему опыту, есть 2 практически одинаковых по скорости способа нахождения первых нескольких миллионов простых чисел:
1. решето Эратосфена,
2. проверка делимости нечетных чисел на уже найденные простые числа (величиной до квадратного корня из тестируемого числа).
Насколько я понимаю суть этих методов одинакова, только подход с разных сторон. И поэтому получается что решето Эратосфена должно потреблять гораздо больше памяти т.к. требует предварительного массива всех чисел меньше максимального искомого.
Т.е. для того что бы найти все простые числа до 1 000 000 нам необходим массив из 999 999 чисел от 2 до 1 000 000, а в случае делимости чисел массив будет состоять только из простых чисел
Или есть какая-то реализация решета не пожирающая память?
Для решета можно использовать битовый массив. Работать будет медленнее, но не знаю, насколько медленнее.

1. В решете делается упор на большое количество простых операций (сложений),
2. Во втором способе упор на небольшое количество медленных операций (деление с остатком).
в смысле считать 1 в бите показателем простого числа, а 0 нет, а потом по номеру бита в массиве определять число?
Честно говоря, с битовыми массивами не работал и насколько сложно реализовать это будет не представляю, но идея передачи этой решетки в виде картинки (bitmap) достаточно интересна))
Да, именно так.

Запись единицы в i-й бит массива a, состоящего из 32-битных чисел:
a[i >> 5] ||= (1 << (i & 31));

Чтение не сложнее. Кстати, можно за раз проверять 32 числа на простоту, сравнивая соответствующую ячейку массива a с 0xffffffff.
Было бы намного интереснее перевести алгоритм в двоичную алгебру. Тогда можно максимально оптимизировать все операции. Современные процессоры имеют расширенные математические команды, которые можно было бы использовать в обход универсальных компиляторов. Я когда давно делал нечто подобное для системы команд x86. Но реализовать подобное на системе команд intel64 было бы намного интереснее.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.