Thanks for this testset, helped me find the bug :)

The same, in a more reusable format:

18
1000000000
999999000
999000999
405
101
1001
10001
100001
1000001
10000001
100000001
555555555
191919191
838383838
123456789
987654321
987654319
101010101

71 999999929
19 999998981
3 5 999000991
3 5 397
101
3 7 991
3 31 9967
3 7 99991
3 19 999979
3 7 9999991
3 67 99999931
3 11 555555541
3 61 191919127
59 838383779
3 29 123456757
2 987654319
987654319
3 19 101010079

/

Edited by author 01.11.2021 14:38

prove it :)

The sum of 2 odd numbers is always an odd number.

To have 2 numbers sum up to an odd number, one needs an even number and an odd number. In this case, 2 + (n-2) (because 2 is the only even prime).

Now, I'm stuck on how to solve the problem fast for even numbers

Test 10 has T=0, take care :)

My accepted program gives: 3 7 1212121

During the contest I also didn't know how to solve it.
I tried to submit dull solution:

1) 3 is enough.
2) The smallest prime number is not more than 500
3) The second prime number is not more than 50000
4) The biggest prime number is any.

...and I had AC.

Just remember that any even number can be presented as sum of two prime numbers, and any odd - as sum of 3 prime numbers.

P.S. As far as I know, this problem is known as Goldbach's Problem...

Edited by author 20.03.2005 22:01

i also have WA#8. here is my code:
program z1356;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var
    n,k,c,i,j,t,p:longint;
const mas :array [1..5133] of longint = (
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,//etc :) last number  49999///
);
procedure init;
begin
 {$IFNDEF ONLINE_JUDGE}
 assign(input,'input.txt');
 reset(Input);
 assign(output,'output.txt');
 rewrite(output);
 {$ENDIF}
end;
procedure print;
begin
{$IFNDEF ONLINE_JUDGE}
 close(input);
 close(output);
{$ENDIF}
 halt(0);
end;
function simple(x:longint):boolean;
var i:longint;
begin
  result:=false;
  if x=1 then exit;
  if x=2 then begin
    result:=true;
    exit;
  end;
  for i:=2 to trunc(sqrt(x)) do
    if x mod i=0 then exit;
  result:=true;
end;
function canbe(x,k,st:longint):boolean;
var i:longint;
begin
  if (x=0) then result:=true else
  if (k=3) then begin
    if simple(x) then begin
        result:=true;
        write(x,' ');
      end
      else result:=false;
  end else
  begin
    canbe:=false;
    while mas[st]>x do
     dec(st);
    for i:=st downto 1 do
      begin
        result:=canbe(x-mas[i],k+1,st);
        if result then
          begin
            write(mas[i],' ');
            exit;
          end;
      end;
  end;
end;
procedure couldbe(t:longint);
var i,k:longint;
begin
  k:=5133;
  while mas[k]>t do dec(k);
  if mas[k]=t then write(mas[k]) else begin
      for i:=k downto 1 do
        if simple(t-mas[i]) then begin
            write(mas[i], ' ',t-mas[i]);
            exit;
        end;
  end;
end;
begin
 init;
 read(n);
 for i:=1 to n do begin
   read(t);
   if odd(t) then
   canbe(t,1,5133) else
   couldbe(t);
   writeln;
 end;
 print;
end.

Write me your code to snipious@mail.ru. I will try help you.

Edited by author 02.01.2007 13:07

very bad english

http://www.ieeta.pt/~tos/goldbach.html is worth seeing.

They are investigating the Goldbach conjecture there.
They say:
Let n be an even number larger than two, and let n=p+q, with p and q prime numbers, p<=q, be a Goldbach partition of n. In order to verify the Goldbach conjecture for a given n, it is sufficient to find one of its Goldbach partitions. Our strategy will be to find the minimal Goldbach partition, i.e., the one that uses the smallest possible prime number p.

They also say:
So far, we have tested all consecutive even numbers up to 2·10^17, and double-checked our results up to 10^17. Some extra intervals were also tested. About 157.3 CPU years were used to do all this. At least 28.2% of the work necessary to reach 10^18 is already done.

So, we may assume when solving this problem that the Goldbach conjecture is true. (It is because upper limit is only 10^9 which is much less than 10^17 :-).

> But how to solve it fast?
> I don't know.
>
Neither do I.
But I tried looking through all even numbers 2..100 000 000 and finding minimal Goldbach partitions for them. The maximal p that I had used was 1093.

More details:
2..100 000 000 -> maxP was 1093
2..10 000 000 -> maxP was 751
2..1 000 000 -> maxP was 523
2..100 000 -> maxP was 293
2..10 000 -> maxP was 173
2..1 000 -> maxP was 73
So, It doesn't seem to grow quickly... If I knew a suitable formula... I could have written a quicker solution.

Anyway, I got AC (http://acm.timus.ru/status.aspx?space=1&pos=867798). Details: 1356 Pascal Accepted 0.031 61 KB.

Please post anything you know on this topic. Are there better ways to find Goldbach partitions? Or are there better ideas on solving this problem?

Special case:
6=3+3
but 9=2+7 not 9=3+3+3

[code deleted]

Edited by moderator 11.03.2006 17:04