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 + 212
15 = 7 + 222
21 = 3 + 232
25 = 7 + 232
27 = 19 + 222
33 = 31 + 212It 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?
Not too tricky. Need to notice that the prime number and the number squared are always less than the composite.
import java.util.*;
public class Euler46
{
public static void main(String[] args)
{
Euler46 e = new Euler46();
System.out.format(“Problem: %s\n”, e.getClass().getName());
System.out.format(“Answer = %s\n”, e.Problem());
}
public String Problem ()
{
ArrayList<Integer> C = new ArrayList<Integer>();
ArrayList<Integer> P = new ArrayList<Integer>();
ArrayList<Integer> T = new ArrayList<Integer>();
int n = 10000;
boolean [] isPrime = new boolean [n+1];
for (int i = 2; i < n; i++)
isPrime[i] = true;
for (int p = 2; p*p < n; p++)
if (isPrime[p] == true)
for (int m = p*p; m < n; m = m+p)
if (m % p == 0)
isPrime[m] = false;
for (int i = 2; i < n; i++)
if (isPrime[i])
P.add(i);
else
if (i % 2 != 0)
C.add(i);
boolean flag = true;
for (int i = 0; i <= C.size()-1; i++)
{
flag = true;
A: for (int p = 0; P.get(p) < C.get(i); p++)
for (int m = 1; m < Math.sqrt(C.get(i)); m++)
if ((P.get(p) + 2*m*m) == C.get(i))
{
flag = false;
System.out.format(“%d: %d + 2*%d^2\n”, C.get(i), P.get(p), m);
break A;
}
if (flag)
T.add(C.get(i));
}
return String.valueOf(T.get(0));
}
}
According to Wiki, every integer greater than one is either a prime number or a composite number.