**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:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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

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

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

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

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++)