|
PROG
|
/* I write the program in C++, but it's not very efficient. I hope someone can improve the algorithm. */ #include <vector> #include <iostream> #include <algorithm> using namespace std; const bool isPRIME[41] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 }; int smartP_3(int n, bool p){ vector<int> arr(n - 1); for(int i = n - 2; i >= 0; --i) arr[i] = i + 2; int cnt = 0, last_i = (n > 2 ? n - 3 : 0); ostream_iterator<int> out(cout, " "); do{ if(!isPRIME[1 + arr[0]] || !isPRIME[1 + arr[n - 2]]) continue; int i = last_i; for(; i < n - 2 && isPRIME[arr[i] + arr[i + 1]]; ++i); if(i == n - 2){ for(i = 0; i < last_i && isPRIME[arr[i] + arr[i + 1]]; ++i); if(i == last_i){ cnt += n; if(p){ cout<<"1 "; copy(arr.begin(), arr.end(), out); cout<<endl; } }else last_i = i; }else last_i = i; }while(next_permutation(arr.begin(), arr.end())); return cnt; } int main() { int n; while(cin>>n){ if(n <= 20 && n > 1){ long start = clock(); cout<<smartP_3(n, false)<<endl; cout<<"Time: "<<(clock() - start)<<" ms"<<endl; } } }
|