Skip to content

Instantly share code, notes, and snippets.

@EmingK
Created September 15, 2015 18:07
Show Gist options
  • Save EmingK/8f6efb3d93e8b0007eaa to your computer and use it in GitHub Desktop.
Save EmingK/8f6efb3d93e8b0007eaa to your computer and use it in GitHub Desktop.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<long long> *primeTable;
long long nextPrime()
{
long long lastPrime = *--(primeTable->end());
do
{
lastPrime += 2;
long long divisionLimit = (long long) sqrt((double)lastPrime);
for (auto divisor : *primeTable)
{
if (divisor > divisionLimit) return lastPrime;
if (!(lastPrime % divisor))
{
break;
}
}
}
while (true);
}
bool isPrime(long long numberToTest)
{
long long knownMaxPrime = *--(primeTable->end());
if (numberToTest == knownMaxPrime)
{
return true;
}
if (numberToTest < knownMaxPrime)
{
int leftIndex = 0, rightIndex = primeTable->size();
while(leftIndex < rightIndex)
{
int middleIndex = (rightIndex+leftIndex)/2;
long long middleNum = (*primeTable)[middleIndex];
if (numberToTest == middleNum) return true;
if (numberToTest > middleNum) leftIndex = middleIndex + 1;
else rightIndex = middleIndex;
}
return false;
}
while (true)
{
knownMaxPrime = nextPrime();
primeTable->push_back(knownMaxPrime);
if (knownMaxPrime == numberToTest)
{
return true;
}
if (knownMaxPrime > numberToTest)
{
return false;
}
}
// you can't excuete to here
throw 233;
return false;
}
long long combine(long long left, long long right)
{
long long _left = left;
long long _right = right;
do
{
_left *= 10;
}
while (_right /= 10);
return _left + right;
}
bool isGood(long long testNum, vector<long long>& numSet)
{
for (auto num : numSet)
{
if (!isPrime(combine(testNum, num)) || !isPrime(combine(num, testNum)))
{
return false;
}
}
return true;
}
struct numberGroupNode
{
vector<long long> numbers;
numberGroupNode *next;
};
void deleteChain(numberGroupNode *node)
{
if (!node) return;
numberGroupNode *currentNode = node;
numberGroupNode *nextNode;
do
{
nextNode = currentNode->next;
delete node;
currentNode = nextNode;
}
while (currentNode);
}
long long solve(int n)
{
if (1==n) return 3;
numberGroupNode** numberGroups = new numberGroupNode*[n];
for (int i=0; i<n; ++i)
{
numberGroups[i] = new numberGroupNode();
}
numberGroupNode *initialNode = new numberGroupNode();
initialNode->numbers.push_back(3);
numberGroups[0]->next = initialNode;
bool solved = false;
long long result = 0;
int currentIndex = 1;
while (true)
{
long long newPrime = (*primeTable)[currentIndex];
numberGroupNode *visitNode;
numberGroupNode *newNode;
for (int i=0; i<n; ++i)
{
visitNode = numberGroups[i];
while (visitNode->next)
{
visitNode = visitNode->next;
if (isGood(newPrime, visitNode->numbers))
{
if (i == n-2)
{
solved = true;
long long sum = newPrime;
for (auto num : visitNode->numbers) sum += num;
result = sum;
for (auto num: visitNode->numbers) cout << num << " ";
cout << newPrime << endl;
break;
}
newNode = new numberGroupNode();
newNode->numbers = visitNode->numbers;
newNode->numbers.push_back(newPrime);
numberGroupNode *nextLevelVisitNode = numberGroups[i+1];
while(nextLevelVisitNode->next) nextLevelVisitNode = nextLevelVisitNode->next;
nextLevelVisitNode->next = newNode;
}
}
if (solved)
{
break;
}
}
if (solved)
{
break;
}
newNode = new numberGroupNode();
newNode->numbers.push_back(newPrime);
visitNode = numberGroups[0];
while (visitNode->next) visitNode = visitNode->next;
visitNode->next = newNode;
++currentIndex;
}
for (int i=0; i<n; ++i) deleteChain(numberGroups[i]);
delete[] numberGroups;
return result;
}
int main()
{
primeTable = new vector<long long>();
primeTable->push_back(3);
isPrime(1000);
cout << solve(5) << endl;
delete primeTable;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment