//////////////////////////////////////////////////////////////////// ////////**************CHALLENGE:Goldbach's Conjecture ////////****************Author: Petros Simidyan //////***************** #include //function fills given inputArr with prime numbers less //or equal to input and hashTable with needed flags, and //returns the number of entrys in primeVec inline int primeArray(int* &inputArr, bool* &hashTable, const int& max) { int* primeVec = new int[max / 2+1]; int count = 0; primeVec[count++]=2; //all boolean values under with prime number indices //like this: //indices:0123456789 //values: 0011010100 //this let us to reduce the searching time to time of O(n) hashTable[2] = true; //initialising vector with prime numbers //with sieve of eratosthenes for (int i = 3; i <= max; i++) { for (int j = 0; j < count; j++) { if (primeVec[j] * primeVec[j] > i) { //if the number is prime we have //to initialise the value in hashtable //under his index with true hashTable[i] = true; primeVec[count++] = i; break; } if (i%primeVec[j] == 0) break; } } delete[] inputArr; inputArr = primeVec; return count; } //function to initialise the given //hasTab of length len with false inline void initBoolArr(bool* &hashTab, const int& len) { for (int i = 0; i < len; i++) hashTab[i] = false; } //function prints result inline void printGoldBach(const int& input) { bool* hashTab = new bool[input]; initBoolArr(hashTab, input); int *primeVec = new int[input / 2]; int numberOfPrimes = primeArray(primeVec, hashTab, input); int curNum = -1; for (int i = 0; i < numberOfPrimes; i++) { curNum = primeVec[i]; if (hashTab[input - curNum]) { std::cout<