10311 - Goldbach and Euler

[Caesum]

No board for this yet, so I am posting here. I have a problem with my program/understanding of what the question is asking for. Can someone just confirm the following input gives the following output ?

Input:

Code: Select all

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
100000000
99999999
99999998
99999997
99999996
99999995
99999994
99999993
99999992
99999991
99999990
99999989
99999988
99999987
99999986
99999985
99999984
99999983
99999982
99999981
99999980
99999979
99999978
99999977
99999976
99999975
99999974
99999973
99999972
99999971
99999970

Output:

Code: Select all

1 is not the sum of two primes!
2 is the sum of 1 and 1.
3 is the sum of 1 and 2.
4 is the sum of 2 and 2.
5 is the sum of 2 and 3.
6 is the sum of 3 and 3.
7 is the sum of 2 and 5.
8 is the sum of 3 and 5.
9 is the sum of 2 and 7.
10 is the sum of 5 and 5.
11 is not the sum of two primes!
12 is the sum of 5 and 7.
13 is the sum of 2 and 11.
14 is the sum of 7 and 7.
15 is the sum of 2 and 13.
16 is the sum of 5 and 11.
17 is not the sum of two primes!
18 is the sum of 7 and 11.
19 is the sum of 2 and 17.
20 is the sum of 7 and 13.
21 is the sum of 2 and 19.
22 is the sum of 11 and 11.
23 is not the sum of two primes!
24 is the sum of 11 and 13.
25 is the sum of 2 and 23.
26 is the sum of 13 and 13.
27 is not the sum of two primes!
28 is the sum of 11 and 17.
29 is not the sum of two primes!
30 is the sum of 13 and 17.
31 is the sum of 2 and 29.
32 is the sum of 13 and 19.
33 is the sum of 2 and 31.
34 is the sum of 17 and 17.
35 is not the sum of two primes!
36 is the sum of 17 and 19.
37 is not the sum of two primes!
38 is the sum of 19 and 19.
39 is the sum of 2 and 37.
40 is the sum of 17 and 23.
41 is not the sum of two primes!
42 is the sum of 19 and 23.
43 is the sum of 2 and 41.
44 is the sum of 13 and 31.
45 is the sum of 2 and 43.
46 is the sum of 23 and 23.
47 is not the sum of two primes!
48 is the sum of 19 and 29.
49 is the sum of 2 and 47.
50 is the sum of 19 and 31.
100000000 is the sum of 49999757 and 50000243.
99999999 is not the sum of two primes!
99999998 is the sum of 49999897 and 50000101.
99999997 is not the sum of two primes!
99999996 is the sum of 49999757 and 50000239.
99999995 is not the sum of two primes!
99999994 is the sum of 49999853 and 50000141.
99999993 is not the sum of two primes!
99999992 is the sum of 49999759 and 50000233.
99999991 is the sum of 2 and 99999989.
99999990 is the sum of 49999783 and 50000207.
99999989 is not the sum of two primes!
99999988 is the sum of 49999847 and 50000141.
99999987 is not the sum of two primes!
99999986 is the sum of 49999753 and 50000233.
99999985 is not the sum of two primes!
99999984 is the sum of 49999921 and 50000063.
99999983 is not the sum of two primes!
99999982 is the sum of 49999991 and 49999991.
99999981 is not the sum of two primes!
99999980 is the sum of 49999921 and 50000059.
99999979 is not the sum of two primes!
99999978 is the sum of 49999877 and 50000101.
99999977 is not the sum of two primes!
99999976 is the sum of 49999667 and 50000309.
99999975 is not the sum of two primes!
99999974 is the sum of 49999843 and 50000131.
99999973 is the sum of 2 and 99999971.
99999972 is the sum of 49999751 and 50000221.
99999971 is not the sum of two primes!
99999970 is the sum of 49999739 and 50000231.

[Adrian Kuegel]

You have to read careful. The remark that 1 is a prime is not the specification of the problem, it is a description of the goldbach conjecture. For the problem it is specified, that all numbers are prime, which are divisible by exactly two positive integers, which means 1 is not prime.
And if you take the sum of two numbers, their difference should be positive, i. e. means >0.

[Caesum]

thanks, solved

[AlexandreN]

For the above input I got the below output:

1 is not the sum of two primes!
2 is not the sum of two primes!
3 is not the sum of two primes!
4 is not the sum of two primes!
5 is the sum of 2 and 3.
6 is not the sum of two primes!
7 is the sum of 2 and 5.
8 is the sum of 3 and 5.
9 is the sum of 2 and 7.
10 is the sum of 3 and 7.
11 is not the sum of two primes!
12 is the sum of 5 and 7.
13 is the sum of 2 and 11.
14 is the sum of 3 and 11.
15 is the sum of 2 and 13.
16 is the sum of 5 and 11.
17 is not the sum of two primes!
18 is the sum of 7 and 11.
19 is the sum of 2 and 17.
20 is the sum of 7 and 13.
21 is the sum of 2 and 19.
22 is the sum of 5 and 17.
23 is not the sum of two primes!
24 is the sum of 11 and 13.
25 is the sum of 2 and 23.
26 is the sum of 7 and 19.
27 is not the sum of two primes!
28 is the sum of 11 and 17.
29 is not the sum of two primes!
30 is the sum of 13 and 17.
31 is the sum of 2 and 29.
32 is the sum of 13 and 19.
33 is the sum of 2 and 31.
34 is the sum of 11 and 23.
35 is not the sum of two primes!
36 is the sum of 17 and 19.
37 is not the sum of two primes!
38 is the sum of 7 and 31.
39 is the sum of 2 and 37.
40 is the sum of 17 and 23.
41 is not the sum of two primes!
42 is the sum of 19 and 23.
43 is the sum of 2 and 41.
44 is the sum of 13 and 31.
45 is the sum of 2 and 43.
46 is the sum of 17 and 29.
47 is not the sum of two primes!
48 is the sum of 19 and 29.
49 is the sum of 2 and 47.
50 is the sum of 19 and 31.
100000000 is the sum of 49999757 and 50000243.
99999999 is not the sum of two primes!
99999998 is the sum of 49999897 and 50000101.
99999997 is not the sum of two primes!
99999996 is the sum of 49999757 and 50000239.
99999995 is not the sum of two primes!
99999994 is the sum of 49999853 and 50000141.
99999993 is not the sum of two primes!
99999992 is the sum of 49999759 and 50000233.
99999991 is the sum of 2 and 99999989.
99999990 is the sum of 49999783 and 50000207.
99999989 is not the sum of two primes!
99999988 is the sum of 49999847 and 50000141.
99999987 is not the sum of two primes!
99999986 is the sum of 49999753 and 50000233.
99999985 is not the sum of two primes!
99999984 is the sum of 49999921 and 50000063.
99999983 is not the sum of two primes!
99999982 is the sum of 49999751 and 50000231.
99999981 is not the sum of two primes!
99999980 is the sum of 49999921 and 50000059.
99999979 is not the sum of two primes!
99999978 is the sum of 49999877 and 50000101.
99999977 is not the sum of two primes!
99999976 is the sum of 49999667 and 50000309.
99999975 is not the sum of two primes!
99999974 is the sum of 49999843 and 50000131.
99999973 is the sum of 2 and 99999971.
99999972 is the sum of 49999751 and 50000221.
99999971 is not the sum of two primes!
99999970 is the sum of 49999739 and 50000231.

is the correct ?

[10153EN]

Before checking the outputs, I wanna ask: "Did you got wrong answer or something other than Accepted?"

[AlexandreN]

Wrong Answer

[Caesum]

that matches what i got for AC.

[Rivaldo]

my program ran over 30s, i just check it from n div 2 to 1.

[Picard]

me too (for the even numbers), but only taking primes into consideration.
this means i first precalculate all possible primes in the range (this is why many solutions require 20Mb or more memory)

[Rivaldo]

No one can help me! I'm very sad about that.

[popel]

I think there are many processes to do it not exceeding TL.
One process is by first enlisting primes<1e4 by sieve process.
Because you need only to check with the primes less than sqrt(x)
to find whether x is a prime.

My program needed 424 KB memory to solve the problem in 19 secs.But surely there are some more high speed algorithms to solve
it in <5 secs with very high memory spent. (25-30 MB)

-Md Tanvir Al Amin

[Rivaldo]

Well, thank you for your help. But I have already used what you said to improve my programme's speed. It got TLE. I am interested why your programmes is so fast. I post my program. I think you can tell me what's the different between yours and mine.
[pascal]
const
name1 = '';
name2 = '';
maxn = 10000;
type
integer = longint;
var
list : array[1 .. maxn] of integer;
l,n : integer;
ouf : text;

procedure get_primes;
var
ck : array[1 .. maxn] of boolean;
i,j : integer;
begin
fillchar(ck, sizeof(ck), true);
for i := 2 to 100 do
if ck then begin
j := i * i;
while j <= maxn do begin
ck[j] := false;
j := j + i;
end;
end;
for i := 2 to maxn do
if ck then begin
inc(l);
list[l] := i;
end
end;

procedure show( a, b : integer);
begin
if a + b = 0 then
writeln(ouf, n, ' is not the sum of two primes!')
else
writeln(ouf, n, ' is the sum of ', a, ' and ', b, '.')
end;

function be_prime( x : integer) : boolean;
var i,j : integer;
begin
j := trunc(sqrt(x));
be_prime := false;
if x = 1 then exit;
for i := 2 to l do
if list > j then break
else if x mod list = 0 then exit;
be_prime := true;
end;

procedure check_odd;
begin
if n = 1 then show(0, 0)
else if be_prime(n - 2) then show(2, n - 2)
else show(0, 0);
end;

procedure check_even;
var i,j : integer;
begin
if n = 2 then show(0, 0)
else begin
j := n div 2; i := n - j; { keep i > j }
if i = j then begin dec(j); inc(i); end;
if not odd(j) and not odd(i) then begin dec(j); inc(i); end;
repeat
if be_prime(j) then
if be_prime(i) then begin show(j, i); exit; end;
j := j - 2;
i := i + 2;
until j <= 0;
show(0, 0);
end;
end;

begin
get_primes;
assign(input, name1);
reset(input);
assign(ouf, name2);
rewrite(ouf);

while not eof do begin
readln(n);
if odd(n) then check_odd
else check_even;
end;
close(input);
close(ouf);
end.
[/pascal]

[Picard]

why do you use 64bit longint? it's much slower and you don't need it here.

[Rivaldo]

Oh, sorry. When I submited it, I deleted it. So it's not the problem.

[Picard]

interesting, when i submited (without the longint) it got accepted in 17.680 seconds