Đôi số thân hòa

[zhaokuangzin]

Tôi muốn tìm những đôi số thân hòa thuộc (1,n).n:longint;
Hai số được gọi là đôi số thân hoà khi tổng ước của số thứ 1 bằng số thứ hai(không kể chính nó) và ngược lại . Tôi viết bằng vòng lặp thì thấy không hiệu quả . Bây giờ tôi muốn lưu trữ 1 tập hợp gồm những số không phải là số nguyên tố rồi mới bắt đầu tìm đôi số thân hòa trong tập hợp này . Mong các bạn hướng dẫn tôi cách lưu trữ tập hợp này .

[zhaokuangzin]

Sao lâu quá mà không ai giải giúp vậy .

[Junior IT]

Cách nhanh nhất là sinh 1 mảng khoảng 500 (hoặc hơn tùy giới hạn N) số nguyên tố, rồi làm việc trên mảng số nguyên tố đó

[zhaokuangzin]

Cám ơn bạn nhưng bài toán về mảng số nguyên tố này tôi giải quyết rồi . Cái tôi nhờ giúp đỡ là tìm các đôi số thân hòa trong khoảng (1,1000000] . Cám ơn

[Junior IT]

Thì mình đang nói về tìm cặp số thân hòa đấy thôi :) Bảng số nguyên tố sẽ giúp bạn tính tổng các ước của một số rất nhanh. [1..1000000] có 40 cặp số thân hòa, chạy khoảng 15s

[zhaokuangzin]

Một mảng chỉ chứa tối đa 37767 phần tử trong khi đó trong khoảng (1,1000000] có nhiều hơn 37767 số nguyên tố .
Bạn có thể thể cho mình xin code của chương trình này không . Cám ơn rất nhiều .

[Junior IT]

Chỉ cần 500 số nguyên tố đầu tiên là tổng đã lớn hơn 1000000 rồi

[zhaokuangzin]

Bạn hiểu nhầm ý của tôi rồi .
Hai số a, b được gọi là đôi số thân hòa khi tổng ước của a (không kể a) bằng b và tổng ước của b bằng a(không kể b). VD : 220 và 284 là đôi số thân hòa .
220=1+2+4+5+10+11+20+22+44+55+110=284
284=1+2+4+71+142=220
Ban đầu tôi muốn tìm 1 tập hợp không phải là số nguyên tố nhưng vẫn không tăng được tốc độ .Bạn có cách nào giúp tôi không ? Cám ơn

[Junior IT]

Ý mình nói là
1. Tìm 1 bảng 500 số nguyên tố đầu tiên
2. for i := 1 to 10^6 do {
t := Tổng_các_ước_số(i);
if (t >=1) and (t <= 10^6) and (Tổng_các_ước_số(t) = i) then writeln(i, ' ' ,t);
}
Bảng số nguyên tố sẽ giúp bạn tính tổng các ước số nhanh hơn và chỉ cần 500 số nguyên tố đầu tiên là đủ

[zhaokuangzin]

Bạn có thể cho tôi ví dụng về việc tính tổng ước của 1 số bằng bảng số nguyên tố không . Cám ơn rất nhiều

[Junior IT]

Ví dụ
Giả sử cần tính tổng của số V


Sum := 1;
for i := 1 to 500 do {
p := prime[i]
if v mod p = 0 then {
t := 1; pp := 1;
while v mod p = 0 do {
v := v div p;
pp := pp * p;
t := t + pp;
}
Sum := Sum * t;
}
}

[zhaokuangzin]

Bạn có thể kiểm tra lại Code trên không ? Cám ơn bạn

[Junior IT]

Code này mình đã test rồi, tất nhiên là nó ko phải toàn bộ chương trình bài làm

[zhaokuangzin]

{------------------------------------------}
Function PrimeNumber(number:longint):boolean;
var i:longint;j:byte;
begin
j:=0;
for i:=2 to number div 2 do
begin
if number mod i=0 then
begin
inc(j);
break;
end;
end;

PrimeNumber:=(j=0);
end;
{-----------------------------------------}
var MangA:Array[0..501]of integer;
v,p,pp,tong,t:longint;
i,j:integer;
begin
v:=28;
tong:=0;
j:=1;
for i:=2 to 2000 do
begin
if PrimeNumber(i)=true then
begin
MangA[j]:=i;
inc(j);
if j=500 then break;
end;
end;


for i:=1 to v do
begin
p:=MangA[i];
if v mod p=0 then
begin
t:=1;
pp:=1;
while v mod p=0 do
begin
v:=v div p;
pp:=pp*p;
t:=t+pp;
end;
tong:=tong+t;
end;
end;
write(tong);
readln;
end.
------------------------------------------------------
Bạn xem dùm tôi đoạn code trên . Tại sao ket quả ra : tong=15 trong khi đúng ra phải là 28

[Junior IT]

{------------------------------------------}
Function PrimeNumber(number:longint):boolean;
var i:longint;j:byte;
begin
j:=0;
for i:=2 to number div 2 do
begin
if number mod i=0 then
begin
inc(j);
break;
end;
end;

PrimeNumber:=(j=0);
end;
{-----------------------------------------}
var MangA:Array[0..501]of integer;
v,p,pp,tong,t:longint;
i,j:integer;
begin
v:=28;
tong:=1;
j:=1;
for i:=2 to 2000 do
begin
if PrimeNumber(i)=true then
begin
MangA[j]:=i;
inc(j);
if j=500 then break;
end;
end;


for i:=1 to v do
begin
p:=MangA[i];
if v mod p=0 then
begin
t:=1;
pp:=1;
while v mod p=0 do
begin
v:=v div p;
pp:=pp*p;
t:=t+pp;
end;
tong:=tong*t;
end;
end;
write(tong-28);
readln;
end.

[zhaokuangzin]

Cám ơn bạn . Bạn có thể nêu phương pháp tìm tổng ước của một số theo cách của bạn bằng lời văn được không . Cách này do bạn nghĩ ra hay là 1 thuật toán có sẵn .

[zhaokuangzin]

Sao lâu quá mà bạn không trả lời giúp tôi .

[Junior IT]

Sorry, mình đang vào thời gian bận :|
Cách tính trên chỉ dựa trên nhận xét phân tích số ra các thừa số nguyên tố thôi

[zhaokuangzin]

Bạn có thể cho 1 VD thực tế được không .
VD :
20 có tổng ước U=1+2+4+5+10=22
20=?

[zhaokuangzin]

Junior IT ơi , bạn có thể trả lời giúp tôi không . Cảm ơn nhiều