โปรแกรม คำนวณหาผลรวมของตัวหารแท้

ตรงเฉลยข้อ 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

[gon]

ครับ
ที่ผมทำไป ทำแบบทื่อ ๆ โดยไม่ได้
ใช้ความรู้คณิตศาสตร์มาเกี่ยวข้องเลยครับ.
คุณอานนท์ท่าทางจะเขียน C เป็นนะครับ.
ผมนึกว่าจะไม่มีคนดูบ้างซะอีก

[tunococ]

ทำไม complexity ไม่ใช่ O(sqrt(x)) เหรอครับ?

ถ้าคำนวณตัวเดียวก็ sqrt(n)
แต่ถ้า n ตัวก็ n*sqrt(n)

[tunococ]

n มันคืออะไรเหรอครับ? เห็นแต่ x?