[Q] Phân tích n thành tổng 2 số nguyên tố

[The_Wall]

Với yêu cầu : tìm hết tất cả các cách phân tích số n cho trước thành tổng của 2 số nguyên tố (nếu được) thì mình sẽ dùng cách gì để tìm dzậy các bác ?

[CrazyBabe]

Hic, chịu, chắc là làm chân phương nhất thui: check all, hì hì.

[consoilangthang]

straight-forward, easy to understand & implement way :

* n lẻ : tối đa một nghiệm. Kiểm tra a = n - 2. Nếu a là số nguyên tố -> add (2, a).

* n chẵn :
thuật giải đơn giản chỉ là duyệt một giá trị nguyên tố a tăng dần (a <= n/2), kiểm tra giá trị hiệu b = n - a xem có phải là số nguyên tố hay không -> add (a, b).

[Mach2]

Thế có phải gọi là brute-force ko hải xói?

[consoilangthang]

số nguyên tố không có tính hàm nên chịu không nghĩ ra cách khác đẹp hơn. Tuy là brute-force nhưng nếu implement khéo ở đoạn kiểm tra số nguyên tố thì performance không tệ đâu.

p/s : CN này đi nha Mach2@. Mày rủ. Tao bao. Tụi nó trả tiền.

[The_Wall]

cách nào hơi chậm nhỉ ? có thể nói chi tiết thêm chút nữa được kô dzậy các bác

[real_time]

Tui viết chương trình mọi người thử xem nhe!
Uses crt;
Var
n:longint;
Funtion nto(n:longint):boolean;
var i,j:integer;
Begin
ngto:=false;
i:=3;
j:=n div 3;
if j mod 2=0 then j:=j+1;
repeat
i:=i+2;
j:=j-2;
until (i>j) or (n mod i=0) or (n mod j = 0);
if i>j then ngto:=true;
End;
Begin
write('cho n: ');readln(n);
n:=n-2;
if not ngto(n) then write('ko the phan tich')
else write('co the');
readln;
end.

[jonhnywalker]

day la 1 van de rat lon cua toan hoc,duoc goi la "gia thuyet Goldbach",do 1 nguoi ten la Goldbach gui cho nha toan hoc Euler
Gia thuyet noi rang:tat ca cac so chan lon hon 2 deu co the viet ra duoi dang 2 so nguyen to
De cho gon,cac nha toan hoc goi ket qua khi chung minh duoc la 1:1,Cac nha toan hoc the gioi van dang dau dau va di nhien la chua chung minh ra duoc.
Ket qua dep nhat ma nhan loai dat toi la 1:2 cua nha toan hoc Tran Canh Nhuan(TQ).
Noi van tat nhu the cho cac ban thay day khong la 1 van de don gian,do vay dung buon khi minh chua tim ra dap an.

[ky_si_khong_dau]

bài này dễ ko ấy mà tui chỉ viết thuật toán ra đay, còn chương trình sau này sẽ post sau vì bây giờ đang bận mà
. Đầu tiên bạn cho một
program giai;
var i,j,n,m:integer;
function nt(x:integer):boolean;
var i:integer;
begin
nt:=true;
for i:=2 to trunc(sqrt(x)) do
if x mod i = 0 then
begin
nt:=false;
break;
end;
end;
{chương trình chính nằm đây nè}
begin
write('Nhap n: ');
readln(n);
for i:=2 to n-2 do
begin
if (nt(i)) and (nt(n-i)) then
begin
writeln(n,'=',i,'+',j);
end;
end.
vậy thui, vậy là tui đã ghi cả chương trình ra đay rồi nhé. Sau đay là phần giả thích:
khi cho i chạy từ 2 đên n-2 thì ta luôn có
n=i+(n-i) lúc này chưa biết i và n-i có phải là nguyên tố không. Nên kiểm tra hai số i và n-i là nguyên tố thì sẽ in ra.
có gì không hiểu tui sẽ giai thích thêm. Bye