1
$\begingroup$

According to Goldbach's conjecture:

Every even integer greater than 2 can be expressed as the sum of two primes.

What is the most efficient algorithm which takes an even number and gives the two prime?

(Please, answer with references.)

$\endgroup$

closed as off-topic by Matthew Conroy, Claude Leibovici, JonMark Perry, TheSimpliFire, Parcly Taxel Feb 14 '18 at 14:02

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Matthew Conroy, Claude Leibovici, JonMark Perry, TheSimpliFire, Parcly Taxel
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Certainly, such algorithm exists, a naive one is to list all prime number lesser than that even number and check summation which of those are our even number. $\endgroup$ – monalisa Feb 13 '18 at 17:14
  • $\begingroup$ This algorithm is the same of mine, It is trivial and inefficient, I need a more efficient algorithm for a decimal number in order of 300 digits. $\endgroup$ – monalisa Feb 13 '18 at 18:18
  • $\begingroup$ I guess sieve of eratosthenes will be quite efficient. When trying to find a decomposition of N, sieve the interval [1,m] and [N-m,N] for sufficiently large m. Then check pairs that remain. Should be quite fast, even for numbers as big as 300 digits $\endgroup$ – Michael Stocker Feb 13 '18 at 18:54
  • $\begingroup$ are you kidding, do you know what happens if the resultant prime numbers would be twin primes in the middle of the interval? In that case, I have tested all numbers! $\endgroup$ – monalisa Feb 13 '18 at 19:10
  • 4
    $\begingroup$ Conjecturally, there will always be a pair with one prime small. Quoting Wikipedia, "3,325,581,707,333,960,528 is the smallest number that has no Goldbach partition with a prime below 9781". Hence we would expect the brute-force search to be somewhat effective. $\endgroup$ – Wojowu Feb 13 '18 at 20:01