Тест Люка - Лемера - C++ Builder - Ответ 7611494

// нахождение остатка от деления на n числа number, возведенного в степень power
unsigned __int64 mod(unsigned __int64 number, unsigned int power, unsigned __int64 n)  // (number ^ power) % n
{
  unsigned __int64 res = 1;
  while (power)
  {
    if (power & 1)  // power % 2
      res = (1ui64 * res * number) % n;
    number = (1ui64 * number * number) % n;
    power >>= 1;  // power /= 2
  }
  return res;
}
//---------------------------------------------------------------------------
// тест Люка - Лемера
bool lucas_lehmer_test(unsigned int q)  // q - простое число, причем q > 2
{
  unsigned __int64 L = 4;  // возможные значения: 4, 10, 52, 724, 970, 10084, ...
  unsigned __int64 mersenne_number = (1ui64 << q) - 1;
  for (unsigned int i = 1; i <= q-2; i++)
  {
    L = mod(L, 2, mersenne_number);
    L += (L < 2) ? mersenne_number - 2 : -2;
  }
  return !L;
}

  unsigned int q = 31;
  String res = "Число " + String((1ui64 << q) - 1);
  if (lucas_lehmer_test(q))
    res += " простое.";
  else
    res += " составное.";
  ShowMessage(res);