LiveStreet

С момента последней статьи пришлось внести несколько оптимизаций, которые уменьшили время нахождения 100000-ного простого числа с 4,552 до 1,224 секунды. И эта разница с ростом чисел будет увеличиваться.
В обе функции я внес следующие оптимизации:
— поиск только по нечетным числам (так как кроме числа 2 больше нет четных простых чисел);
— находим корень числа для конечного диапазона не каждый раз в цикле, а только когда это необходимо;
— для проверки числа на простоту делим только на нечетные числа.
Первая функция. Если число, которое мы передали в функцию, простое, функция возвратит 1, если нет, то 0.

int PrimeNumber(int number)
{
  int MaxNumber;

  // отсеиваем все четные числа
  if (number%2 == 0 && number != 2)
  {
    return 0;
  }
  if (number == 2)
  {
    return 1;
  }

  // находим последний элемент цикла, до которого будем делить число для проверки на простоту
  MaxNumber = sqrt(number)

  for (int i=3; i<MaxNumber; i+=2)
  {
    // проверяем наше число на остаток по всем нечетным числам начиная от тройки
    if (number%i == 0)
    {
      return 0;
    }
  }

  return 1;
}

Вторая функция. Эта функция находит первое простое число, которое находится за числом, которое мы передаем в функцию.

int NextPrimeNumber(int previous)
{
  int temp;
  int MaxNumber;
  int i = 3;

  if (previous == 2)
  {
    return 3;
  }
  else
  {
    temp = previous + 2; // идем только по нечетным числам
  }

  MaxNumber = sqrt(temp);

  while (1)
  {
    if (temp%i == 0 && i!=temp)
    {
      temp += 2;
      MaxNumber = sqrt(temp);
      i=3;
      continue;
    }

    if (i>MaxNumber)
    {
      break;
    }

    i += 2;
  }

  return temp;
}

Палиндромы
В проекте «Эйлер» попалась задачка, в которой встретил такое понятие как палиндром. Это числа, которые читаются в обоих направлениях одинаково (1001, 55, 474, 2, 12521...). Я написал функцию, которая проверяет, является ли число палиндромом.
Если число, которое мы передаем в в функцию GetPalindrome(), является палиндромом, функция возвращает единицу, если нет — ноль.

int GetPalindrome(int pal)
{
  int next = 0;
  int pal2 = pal;

  while (pal2 != 0)
  {
    next = (next * 10) + (pal2 % 10);
    pal2 /= 10;
  }

  if (pal == next)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}