OJ Board

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> vec;
vector<int> prime;
vector<int> neighbor[17];
int used[17];

void printList();

void prime_generator(){

  int i,j;
  bool isPrime;
  int num;

  prime.clear();
  prime.push_back(2);
  for(j=3; j<100; j=j+2){
    isPrime = true;
    for (i=0; (prime.at(i)*prime.at(i)) <= j;  i++) {  //skips 0th prime            
      if ((j%prime.at(i)) == 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime){
      prime.push_back(j);
      //      primes[num_primes++] = j;
    }
  }   //end outer for                                                           
}


void erase (int cnt){
  int i;

  vector<int>::iterator result;
  result = find( vec.begin(), vec.end(), cnt );
  vec.erase(result);
}


bool isPrime(int num){
  vector<int>::iterator result;
  result = find(prime.begin(), prime.end(), num);
  if (result == prime.end())  //can't find prime number
    return false;
  else
    return true;
}


void checkPrime(){
  int i = 0;
  int num;
  bool p = true;

  i = vec.size()-1;
  num = vec.at(i) + vec.at(0);
  if (isPrime(num))
    printList();  
}


void printList(){
  int i;
  for (i=0; i<vec.size(); i++)
    cout<<vec.at(i)<<" ";
  cout<<endl;
}

void print(int cnt, int n){
  int i,j,k;
  int num;
  
  vec.push_back(cnt);
  used[cnt] = 1;
  if (vec.size() == n)
    checkPrime();
  
  //search all of the current node's possible neighbors from neighbor[17]
  
  for (i=0; i<neighbor[cnt].size(); i++){
    num = neighbor[cnt].at(i);
    if (num <= n){
      if (used[num] == 0)
	print(num, n);
    }
  }
  //not in its neighbors
  erase(cnt);
  used[cnt] = 0;
}


void calc_nbrs(){  //calculate neighbors that will get a prime sum
  int i, j;
  int sum;

  for (i=0; i<17; i++)
    neighbor[i].clear();
  
  for (i=1; i<=16; i++){
    if (i % 2 == 0){
      for (j=1; j<=16; j+=2){
	sum = i+j;
	if (isPrime(sum))
	  neighbor[i].push_back(j);
      }
    }
    else{
      for (j=2; j<=16; j+=2){
	sum = i+j;
	if (isPrime(sum))
	  neighbor[i].push_back(j);
      }
    }
  }//end for i
}//end calc_nbrs;

void init_array(){
  for (int i=0; i<17; i++){
    used[i] = 0;
  }
}


int main(){
  int n, i, j;
  int counter = 1;


  prime_generator();
  calc_nbrs();

  cin>>n;
  
  while (!cin.eof()){
    vec.clear();
    init_array();
    cout<<"Case "<<counter<<":"<<endl;
    counter++;
    print(1,n);
    cin>>n;
    if (!cin.eof())
      cout<<endl;
  }

  return 0;
}

Code: Select all

prime.clear();

Code: Select all

prime.erase(prime.begin(), prime.end());