Re: [問題] 找出所有因數的演算法

[waterdisney (飛過鷹族的訕笑)]

※ 引述《dgf130 (JoyChen)》之銘言：
: ※ 引述《buoyance (buoyance)》之銘言：
: : design an algorithm for finding all the factors of a positive integer
: factors( int num )
: {
:         printf("%d factors are ",num);
:         for( int i = 1; i <= num; i++ )
:                 if( num%i )
:                         printf( "%d, ",i );
: }
: 就檢查1~自己本身的數能不能整除就好啦～應該不難
  dgf130說的是一種作法。
  可是如果真的這樣寫，時間複雜度為 O(n)

  一般來說，for迴圈的條件終止式可檢查至 sqrt(n) 即可。

  即  for(int i=1;i<=sqrt(n);i++){
        if(num % i){
            printf("%d,%d",num,n/num);
        }
      }

  sqrt(n)的意思是  「對n取根號」



  另外。此種寫法，仍不盡理想。
  最好的作法為利用dynamic programming
  採動態填表的方式求n的所有因數。
  如此於程式重複執行時，可不用重複計算之前已經做過的檢查..

  至於dynamic programming怎麼寫...
  這個..翻書比較快。bbs講不清楚。 XD

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 125.233.70.185
推 dgf130:因為題目說是找一個正整數的所有因數..所以應該這樣就可以ꐠ
→ dgf130:找多數個正整數的因數..才需要用到DP吧？殺雞焉用牛刀?.@@
推 waterdisney:原po題目為"design an algorithm" 他要的是演算法~
→ waterdisney:所以...XD XD
推 buoyance:謝謝兩位的解答喔!!
推 dgf130:演算法不就是作法嗎...小弟駑鈍..不知道差在哪裡..囧rz
推 Daiblo2:演算法都是用虛擬碼寫  這樣會比較好一點