Простое число - это натуральное число больше единицы, которое делиться только на единицу и само на себя.

Из определения простого числа следует и алгоритм: Будем считать сколько делителей у заданного числа в диапазоне от единицы до самого себя и если таких делителей два, то исходное число простое:

 count := 0;
 for d := 1 to n do
  if n mod d = 0
   then inc(count);
 if count = 2
  then <Число n простое>
  else <Число n не простое>

Ка видим все просто!
PS: Исходное число заведомо должно быть больше единицы, если это не так, то прежде чем запускать выше описанный алгоритм, следует поставить условие и если исходное число меньше или равно единице, то можно смело утверждать, что оно не простое без всяких дальнейших проверок!

Выше описанный алгоритм хоть и правильно определит является ли заданное число простым, на практике используется редко в силу своей неэффективности. Если исходное число 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 не простое>

И если делителей не нашлось в указанном диапазоне значений делителя, то исходное число является простым.

Сократив число итераций вдвое, мы практически вдвое улучшили алгоритм, но и это еще не предел. А что если исходное число поделилось на два в первой же итерации, то зачем тогда дальнейшая проверка? Следовательно, откажемся от цикла с параметром в пользу цикла с условием:

 d := 2;
 count := 0;
 while (count = 0) and (d <= n div 2) do
  if n mod d = 0
   then inc(count)
   else inc(d);
 if count = 0
  then <Число n простое>
  else <Число n не простое>

Это уже что-то! Наш алгоритм достаточно быстро проверяет, является ли число простым, так как большая часть чисел не простые, но если так встречается большое простое число, то проверка идет до конца и значительно долго!
Нет ли способа и тут сократить число итераций? Оказывается есть!

Из математики известно, что наименьший делитель натурального числа, если он существует, меньше либо равен корню квадратному исходного числа. А это означает, что если мы будем искать делитель в диапазоне от 2 до корня квадратного исходного числа, и не найдем его, то можно утверждать, что исходное число является простым!

 d := 2;
 count := 0;
 while (count = 0) and (d <= sqrt(n)) do
  if n mod d = 0
   then inc(count)
   else inc(d);
 if count = 0
  then <Число n простое>
  else <Число n не простое>

Как и в предыдущих случаях мы предполагали, что исходное число больше единицы. Мы пришли практически к совершенному алгоритму проверки простого числа, который выполняет свою работу за приемлемое время. Например, если исходное число равно 1 млрд, то за не более чем 1000 итераций мы может с уверенностью сказать простое ли исходное число или нет!

И наконец, мы готовы записать наиболее совершенный алгоритм проверки числа. Нам уже не важно сколько делителей, один или несколько, нужен хотя бы один, чтобы сделать вывод, что число не простое. Поэтому заменим счетчик числа найденных делителей флагом - переменная логического типа, которая будет признаком "простоты" числа. Кроме того, мы уберем требование, что исходное число должно быть больше единицы, изначально присвоив флагу значение false, если это не так, и заменим вычисление корня квадратного, умножением:

 d := 2;
 flag := (n > 1);
 while (flag) and (d * d <= n) do
  begin
   f := n mod d <> 0;
   inc(d);
  end;
 if flag
  then <Число n простое>
  else <Число n не простое>

Или на C/C++

 int d = 2;
 bool flag = n > 1;
 while (flag && d * d <= n)
   f = n % d++ != 0;
 if (flag)
  <Число n простое>
 else <Число n не простое>

Мы потрудились на славу! Создан алгоритм, который за приемлемое время проверяет является ли заданное число простым или нет!

Для закрепления темы "Простые числа" разберем задачу: Определить количество делителей заданного натурального числа.

Очевидно, что задачу можно решить перебрав все делители от единицы до самого числа и если исходное число делится без остатка на текущий делитель, то увеличиваем счетчик делителей на единицу.

Однако этот алгоритм по выше описанным причинам непригоден на практике. Решим эту задачу иначе: Найдем все делители, значения которых не превышают корня квадратного от заданного числа. Остальные делители - это результат деления исходного числа на уже найденный делитель из диапазона от двух до корня квадратного делимого. Исключением может составлять, случай когда делитель точно равен корню квадратному исходного числа.

И как и ранее, мы за приемлемое время вычислим все делители и их количество. Алгоритм очевиден:

 d := 2;
 flag := (n > 1);
 count := 0;
 while (flag) and (d * d <= n) do
  begin
   count := count + byte(n mod d = 0);
   inc(d);
  end;

Мы нашли количество делителей заданного числа в диапазоне от двух до корня квадратного включительно! К этому числу надо прибавить единицу, так как на единицу исходное число тоже делится. Теперь определим количество делителей в диапазоне от корня квадратного до самого числа - а их столько же, сколько и в первом диапазоне, до корня квадратного!
Следовательно всего количество делителей (count + 1) * 2, но делитель, значение которого равно корню квадратному исходного числа в этом счете присутствует дважды! Поэтому, если существует делитель, равный корню квадратному из исходного числа, то из общего числа делителей следует вычесть единицу.

Задача решена!