Вычисление простых чисел на шаблонах C++

В этом посте я расскажу как сделать совершенно бесполезную вещь — вычислять простые числа при помощи шаблонов C++.

Алгоритмы проиллюстрированы кодом на Scheme, поэтому осторожно: скобочки!

Управляющие конструкции

Мы хотм получить compile-time аналог функции. В программировании на шаблонах в качестве функции выступает структура, параметры шаблона которой отвечают аргументам функции, а константные статические члены — результатам.

(define (f x)
  (* x x))

(f 10) ; => 100

Аналогичный код на C++:

template<int x>
struct f
{
  static const int value = x * x;
};

«Вызов» такой функции происходит через инстанцирование шаблона:

int main()
{
  std::cout << f<10>::value << std::endl; // 100
}

Шаблоны C++ позволяют обрабатывать некоторые значения параметров шаблона особым образом (специализация). Это позволяет организовать условную управляющую конструкцию:

(define (g x)
  (if (= x 0)
      42
      (* x x)))
(g 10) ; => 100
(g 0) ; => 42

template<int x>
struct g
{
  static const int value = x * x;
};

template<>
struct g<0>
{
  static const int value = 42;
};

int main()
{
  std::cout << g<10>::value << std::endl; // 100
  std::cout << g<0>::value << std::endl; // 42
}

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

Вычисление простых чисел

Постановка задачи

Мы хотим получить функцию, которая возвращает i-e простое число:

int main()
{
  std::cout << prime<0>::value << std::endl; // 2
  std::cout << prime<1>::value << std::endl; // 3
  std::cout << prime<2>::value << std::endl; // 5
  std::cout << prime<3>::value << std::endl; // 7
  // ...
}

Проверка на простоту

Сразу такую функцию реализовать не получится, нужно начать с чего-то более простого. Проще всего проверить, является ли некоторое n простым числом. Для проверки проверяем, что остаток от деления n на все числа от n-1 до 1 не равен нулю.

(define (is-prime n)
  (is-prime-rec n (- n 1)))

(define (is-prime-rec n div)
  (if (or (= div 1) (= div 0))
      #t
      (and (not (= 0 (remainder n div)))
           (is-prime-rec n (- div 1)))))

(is-prime 2) ; => #t
(is-prime 3) ; => #t
(is-prime 4) ; => #f
(is-prime 5) ; => #t

template<int n, int div>
struct is_prime_rec
{
  static const bool value = (n % div != 0) && is_prime_rec<n, div - 1>::value;
};

template<int n>
struct is_prime_rec<n, 1>
{
  static const bool value = true;
};

template<int n>
struct is_prime_rec<n, 0>
{
  static const bool value = true;
};

template<int n>
struct is_prime
{
  static const bool value = is_prime_rec<n, n - 1>::value;
};

int main()
{
  std::cout << is_prime<1>::value << std::endl; // 1
  std::cout << is_prime<2>::value << std::endl; // 1
  std::cout << is_prime<3>::value << std::endl; // 1
  std::cout << is_prime<4>::value << std::endl; // 0
  std::cout << is_prime<5>::value << std::endl; // 1
  std::cout << is_prime<6>::value << std::endl; // 0
  std::cout << is_prime<7>::value << std::endl; // 1
}

Вопрос о том, считать ли 1 простым числом оставим открытым, но в данной реализации проверки 1 считается простым.

Нахождение следующего простого числа

Определим функцию, которая находит наименьшее простое число, большее заданного (то есть, следующее).

(define (next-prime n)
  (if (is-prime (+ n 1))
      (+ n 1)
      (next-prime (+ n 1))))
(next-prime 2) ; => 3
(next-prime 3) ; => 5
(next-prime 5) ; => 7
(next-prime 7) ; => 11

template<int n>
struct next_prime;

template<int n, bool cond>
struct next_prime_if
{
  static const int value = n + 1;
};

template<int n>
struct next_prime_if<n, false>
{
  static const int value = next_prime<n + 1>::value;
};

template<int n>
struct next_prime
{
  static const int value = next_prime_if<n, is_prime<n + 1>::value>::value;
};

int main()
{
  std::cout << next_prime<1>::value << std::endl; // 2
  std::cout << next_prime<2>::value << std::endl; // 3
  std::cout << next_prime<3>::value << std::endl; // 5
  std::cout << next_prime<4>::value << std::endl; // 5
  std::cout << next_prime<5>::value << std::endl; // 7
  std::cout << next_prime<6>::value << std::endl; // 7
  std::cout << next_prime<7>::value << std::endl; // 11
}

Нахождение просто числа по номеру

Что такое i-e простое число? Это следующее за (i-1)-м:

(define (prime i)
  (if (= i 0)
      2
      (next-prime (prime (- i 1)))))
(prime 0) ; => 2
(prime 1) ; => 3
(prime 2) ; => 5
(prime 3) ; => 7

template<int i>
struct prime
{
  static const int value = next_prime<prime<i - 1>::value >::value;
};

template<>
struct prime<0>
{
  static const int value = 2;
};

int main()
{
  std::cout << prime<0>::value << std::endl; // 2
  std::cout << prime<1>::value << std::endl; // 3
  std::cout << prime<2>::value << std::endl; // 5
  std::cout << prime<3>::value << std::endl; // 7
  std::cout << prime<4>::value << std::endl; // 11
  // ...
}

Полный исходный код:
Scheme pastebin.com/21VFjYt0
C++ pastebin.com/cfSvBRNH