[Malleys]

рони,
ваш алгоритм считает 2 и 3 за составные числа.

Оптимальнее проверять не все делители подряд от 2 до sqrt(N), а только простые делители. Например, если мы проверили делимость на 2, то нет необходимости проверять остальные числа кратные 2. (Т. е. нужно тогда проверить только 2, 3, 5, 7, 9, ..., sqrt(N) )

Можно уменьшить количество делителей предприняв тот же шаг для следующего простого числа -- 3. Тогда у нас останутся числа не кратные 2 и 3. (Теперь нужно проверить только 2, 3, 5, 7, 11, 13, 17, 19, ..., sqrt(N)) Легко заметить, что после 2 и 3 идут числа вида 6n ± 1

Т. е. после того как нашли наибольший делитель sqrt(N), необходимо его привести к виду 6n ± 1. Полученный делитель должен быть меньше либо равен sqrt(N).

function isPrime(number) {
  // простые числа 2 и 3
  if(number == 2 || number == 3)
	  return true;

  // определяем составные числа:
  // кратные 2 и 3 больше 1, остаются числа вида 6n ± 1, где n > 0, n ∈ Z
  if(number < 2 || number % 2 == 0 || number % 3 == 0)
	  return false;

  // steps[остаток от деления делителя на 6] == число, на которое увеличить делитель, чтобы получилось число вида 6n ± 1
  var steps = [-1, -2, -1, -2, -3, -4];

  // делитель приводим к виду 6n ± 1
  var i = Math.sqrt(number) | 0;
  var divider = (i - (i - 5) % 2 - 2 * (1 - Math.ceil(((1 + ((i - 5) / 2) | 0) % 3) / 2)));
  return isPrime(number, divider);

  function isPrime(number, divider) {
	  divider = divider;

	  // проверили все делители и пришли сюда?
	  // значит число простое
	  if(divider == 1) return true;

	  // после того как проверили делимость на 5,
	  // делаем вывод (на 2 и 3 нет смысла проверять,
	  // т. к. здесь могут быть только не кратные 2 и 3)
	  return number % divider == 0 ? false : divider == 5 ? true : isPrime(number, divider + steps[divider % 6]);
  }
}

alert([22, 23].map(function(v) {
	return v + " " + isPrime(v)
}).join("\n"));

Поскольку от 6n до 6(n + 1) только два числа не кратных 2 и 3, то на каждые 6 чисел из ряда 2, ..., sqrt(N) алгоритм выбирает 2 числа.
Это означает, что для проверки числа по этому алгоритму необходимо в 3 раза меньше делителей, чем в ряду 2, ..., sqrt(N)