<อานนท์>
03 มิถุนายน 2001, 03:48
ตรงเฉลยข้อ 5 (http://www.mathcenter.net/ntheory/ntheory01/ntheory01p04.html) ของแบบฝึกหัดในเรื่องทฤษฎีจำนวนบทที่ 1 (http://www.mathcenter.net/ntheory/ntheory01/ntheory01p01.html) หนะครับ
ตรงส่วนที่คำนวณหาผลรวมของตัวหารแท้หนะครับ
long y = 0;
for (long i = 1; i<=(x/2); i++)
if ((x%i) == 0) y += i;
ผมสามารถคิดวิธีที่คำนวณได้เร็วกว่านี้ครับ
ผมลองใช้ perl เขียนได้อย่างนี้ครับ
my $y = 1; my $temp = sqrt($x);
for (my $i = 2; $i < $temp; $i++) {
use integer;
if (($x%$i) == 0) { $y += $i + $x/$i; };
};
if (int($temp) == $temp) { $y += $temp; };
ถ้าใช้ภาษา C ก็คงออกมาเป็นอย่างนี้ครับ
long y = 1; float temp = sqrt(x);
for (long i = 2; i < temp; i++) {
if ((x%i) == 0) y += i + x/i;
};
if (int(temp) == temp) y += temp;
ตัวที่เป็นภาษา C ยังไม่ได้ทดสอบครับว่ามี bug รึเปล่า
แต่ตัวที่เป็น perl นั่นลองรันทดสอบแล้วครับ
ถ้าเป็นแบบที่เฉลยไว้จะใช้ time complexity เป็น O(x^2) ครับ
แต่วิธีที่ผมใช้นั้นใช้เวลาเป็น O(x*sqrt(x)) ครับ
เช่นกันครับ วิธีนี้สามารถใช้ได้กับโจทย์ข้อ 2 และข้อ 6
ตรงส่วนที่คำนวณหาผลรวมของตัวหารแท้หนะครับ
long y = 0;
for (long i = 1; i<=(x/2); i++)
if ((x%i) == 0) y += i;
ผมสามารถคิดวิธีที่คำนวณได้เร็วกว่านี้ครับ
ผมลองใช้ perl เขียนได้อย่างนี้ครับ
my $y = 1; my $temp = sqrt($x);
for (my $i = 2; $i < $temp; $i++) {
use integer;
if (($x%$i) == 0) { $y += $i + $x/$i; };
};
if (int($temp) == $temp) { $y += $temp; };
ถ้าใช้ภาษา C ก็คงออกมาเป็นอย่างนี้ครับ
long y = 1; float temp = sqrt(x);
for (long i = 2; i < temp; i++) {
if ((x%i) == 0) y += i + x/i;
};
if (int(temp) == temp) y += temp;
ตัวที่เป็นภาษา C ยังไม่ได้ทดสอบครับว่ามี bug รึเปล่า
แต่ตัวที่เป็น perl นั่นลองรันทดสอบแล้วครับ
ถ้าเป็นแบบที่เฉลยไว้จะใช้ time complexity เป็น O(x^2) ครับ
แต่วิธีที่ผมใช้นั้นใช้เวลาเป็น O(x*sqrt(x)) ครับ
เช่นกันครับ วิธีนี้สามารถใช้ได้กับโจทย์ข้อ 2 และข้อ 6