# Goldbach’s Conjecture

Goldbach’s conjecture – Every even integer greater than 2 can be represented as the sum of two primes numbers.

Example:

Given Number : 200

```Prime Numbers are 3 197
Prime Numbers are 7 193
Prime Numbers are 19 181
Prime Numbers are 37 163
Prime Numbers are 43 157
Prime Numbers are 61 139
Prime Numbers are 73 127
Prime Numbers are 97 103
```

Approach:

• Check if number if not even, return.
• Check if number is less than 2, return.
• Navigate i, from 3 to number check if i and (x-i) is prime, if yes, Print it

Code:

 public class GoldbachConjecture { public static void Goldbach(int x) { if (x % 2 != 0) { System.out.println("Not Even"); return; } if (x <= 2) { System.out.println("Less than 2"); return; } for (int i = 3; i < x / 2; i++) { if (isPrime(i) && isPrime(x – i)) { System.out.println("Prime Numbers are " + i + " " + (x – i)); } } } public static boolean isPrime(int x) { for (int i = 2; i < x / 2; i++) { if (x % i == 0) { return false; } } return true; } public static void main(String[] args) { Goldbach(100); } }

```Output :
Prime Numbers are 3 97
Prime Numbers are 11 89
Prime Numbers are 17 83
Prime Numbers are 29 71
Prime Numbers are 41 59
Prime Numbers are 47 53
```

### 4 thoughts on “Goldbach’s Conjecture”

1. Nice Approach! But can this be improved using memoization (DP)?

2. we could increment 2 instead one each time. (3, 5, 7, 9 …) . Even numbers are not going to be prime

3. I believe We have to check upto sqrt(x) not x/2

4. for (int i = 3; i < x / 2; i++) {

needs to be corrected to

for (int i = 1; i <= x/2; i++)

And this needs to be corrected

for (int i = 2; i < x / 2; i++) {

to

for (int i =2; i <= number/2; i++)