problem 46

/*
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
*/
#include <iostream>
#include<vector>
#include<cmath>
using namespace std;

bool is_prime(int num){
  for (int i = 3; i < int(pow(num, .5)) + 1; i += 2){
    if (num % i == 0){
     return false;
    } 
  }
  return true;
}

int main() {
  vector<int> primes = {2};
  int number = 3;
  while (number < 10000){
    bool check = 1;
    if (is_prime(number)){
      primes.push_back(number);

    }
    else{
     for(int i = 0; i < primes.size(); i++){
       int x = (pow(((number - primes[i]) / 2), 0.5));
        if (pow(((number - primes[i]) / 2), 0.5) == x ){
          check = 0;
         break;
        }
      } 
      if(check){
         cout << number <<endl;
         return 0;
      }
    }
   number += 2;
  }
return 0;
}