Recursive function memo

feb7.cpp

#include <iostream>

// Auxiliary functions of is_prime
bool has_divisor(int N, int i) {
  // Base
  // 0ならば対象の整数がないまたは、i == Nなら自分(と1)以外約数が存在しない。
  if (i == N) return false;
  // i~N-1までの範囲で約数が存在する。
  if (N % i == 0) return true;
  // Recursive
  return has_divisor(N, i+1);
}

bool is_prime(int N) {
  if (N == 1) return false; // 素数じゃない
  else if (N == 2) return true; // 素数
  // 2~N-1の範囲に約数がなければNは素数。
  else return !has_divisor(N, 2);
}


int main() {
  std::cout << is_prime(0) << std::endl;
  
  std::cout << is_prime(1) << std::endl;
  
  std::cout << is_prime(2) << std::endl;
  
  std::cout << is_prime(5) << std::endl;
  
  std::cout << is_prime(13) << std::endl;
  
  std::cout << is_prime(57) << std::endl;
}

/* output
0
0
1
1
1
0
*/