USACO 1.5 SuperPrime Rib

A straight forward combination generation problem that can be solved using DFS / Backtrack technique.

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

bool isPrime(int number) {
  if (number == 3 || number == 5) return true;

  if (number % 3 == 0 || number % 5 == 0) return false;

  int m = sqrt(number);
  for (int i = 2; i <= m; ++i) {
    if (number % i == 0) return false;
  }

  return true;
}

void dfs(int index, int N, vector<int> &prev, ofstream &fout) {
  vector<int> candidate;
  if (N == 1) {
    candidate = {2, 3, 5, 7};
    for (auto &item : candidate)
      fout << item << endl;
    return;
  }

  if (index == N) {
    for (auto &item : prev)
        fout << item << endl;
    return;
  }

  candidate = {1, 3, 7, 9};
  vector<int> tmp;
  for (auto &item : prev) {
    for (auto &number : candidate) {
      auto i = item * 10 + number;
      if (isPrime(i))
        tmp.push_back(i);
    }
  }

  if (tmp.size())
    dfs(index + 1, N, tmp, fout);

}

int main() {
  ifstream fin("sprime.in");
  ofstream fout("sprime.out");

  int N;
  fin >> N;

  vector<int> prev = {2, 3, 5, 7};
  dfs(1, N, prev, fout);
  return 0;
}