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:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • Maverick

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

  • Sathiyaseelan

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

  • Sathiyaseelan

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

  • lipsa patel

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

%d bloggers like this: