Теорема Вильсона

Материал из Википедии — свободной энциклопедии

Теорема Вильсона — теорема теории чисел, которая утверждает, что

Практическое использование теоремы Вильсона для определения простоты числа нецелесообразно из-за сложности вычисления факториала.

[править] История

Теорема впервые была сформулирована Варингом (англ.) в 1770 году и принадлежала, по его словам, Вильсону (англ.). Доказал её Лагранж в 1771 году.

[править] Информатика

Реализация алгоритма на языке программирования С++:

int factorial(int x) {
    if( x == 0 ) return 1;
    return x * factorial (x - 1);
}
bool simpleInt (int p)
{
  return ((factorial (p-1)+1)%p==0);
}

Где функция factorial () находит факториал рекурсивным методом, а simpleInt () - считает логическое выражение и возвращает false, если число составное, true, если число простое.

[править] Литература

• Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
• Трост Э. Простые числа, пер. с нем., М., 1959
• Виноградов И. М. Основы теории чисел. — 5 изд.. — М.-Л.: Гостехиздат, 1952.