Лічильник
Сьогодні Разом
Відвідувань 313 5266013
Авторізацій 48 421853
Користувачів 39 2716
Статья

36. Улучшение алгоритма проверки простого числа


Выше описанный алгоритм хоть и правильно определит является ли заданное число простым, на практике используется редко в силу своей неэффективности. Если исходное число n очень большое, порядка миллиардов или даже более, то требуется такое же число сравнений, на что уходит много времени.

Данный алгоритм можно улучшить:

Во-первых, нет смысла делить на единицу и само на себя, так как все числа делятся на единицу и на само себя. Следовательно можно искать делители в диапазоне от 2 до n-1. Правда мы с экономили только на двух итерациях и это значительно не улучшит временные показатели алгоритма.
Во-вторых, а есть ли смысл искать делители, когда делитель больше половины делимого? Конечно же нет! Следовательно, мы уменьшим число итерация вдвое:
 count := 0;
 for d := 2 to n div 2 do
  if n mod d = 0
   then inc(count);
 if count = 0
  then <Число n простое>
  else <Число n не простое>
И если делителей не нашлось в указанном диапазоне значений делителя, то исходное число является простым.