使用theta（n）效率打印除數

我正在努力實現這個正確的。我想創建一個函數來確定用戶輸入userNum的所有除數，並將它們輸出給用戶。當userNum = 16我得到的輸出1 16 2 8.我沒有想到命令是正確的，但我錯過了4，並努力找出原因。有什麼想法嗎？我試圖在theta（sqrt（num））效率中做到這一點。使用theta（n）效率打印除數

void PrintDivisors(int num); 

int main() 
{ 
    int userNum; 

    //Request user number 

    cout << "Please input a positive integer >=2:" << endl; 
    cin >> userNum; 

    PrintDivisors(userNum); 

    return 0; 
} 

void PrintDivisors(int num) 
{ 
    int divisorCounter; 

    for (divisorCounter = 1; divisorCounter < sqrt(num); divisorCounter++) 
    { 
     if (num % divisorCounter == 0 && num/divisorCounter != divisorCounter) 
      cout << divisorCounter << endl << num/divisorCounter << endl; 
     else if (num % divisorCounter == 0 && num/divisorCounter == divisorCounter) 
      cout << divisorCounter << endl; 
    } 
}

更新：我把所有的數字印刷，但仍在試圖確定如何將其打印出來，以便同時THETA開方內剩餘的（n）的效率

來源

2017-02-23 StormsEdge

divisorCounter

@huck_cussler對不起我不是以下。這就是我在我的循環沒有？ – StormsEdge

是的，那是你停止循環的條件。當num爲16時，考慮這種情況的含義。 –

請務必仔細檢查你的邊界條件。

什麼是sqrt(num)？
最大的divisorCounter什麼是通過for循環測試？
4會通過測試嗎？

我想如果仔細看看這三條問題，你會壓扁這個bug。

來源

2017-02-23 22:42:52

我已經得到它的功能正常，因爲除數。努力按照正確的順序輸出它們。我不確定只有一個for循環可以完成它 – StormsEdge

在for循環中打印較低的除數，並且（如果得到的較大除數不相同 - 即非平方根），則將較大的除數加上運行串。對於16，打印1，在（最初是空的）字符串上加上16。打印2，前置8.打印4，不要預先打印其他4.不打印第二個循環，只打印收集的字符串（8 16）。這擺脫了第二個循環。就我個人而言，我認爲收集數組中的數字並將它們反向打印（第二循環）看起來更便宜，並且仍然是O（sqrt n）。 –

變化循環的終止條件操作<=，現在你會看到4。

擺脫sqrt函數調用。更好的使用這個循環

for (divisorCounter = 1; divisorCounter * divisorCounter <= num; divisorCounter++)

來源

2017-02-23 23:04:59

對於使得它在運行的sqrt（n）的時間複雜度：

對於任何N = A X b的。可以是< = sqrt（n）或b < = sqrt（n）。所以，如果你能找到範圍[1，sqrt（n）]內的所有除數，你可以找到大於sqrt（n）的其他除數

可以使用for循環遍歷範圍1到sqrt（n）並找到小於sqrt（n）的所有除數，同時您還可以使用它來查找大於（或等於）sqrt（n）的其他數字。

假設數字i < sqrt（n）是除數或n。在這種情況下，數字k = n/i也將是n的除數。但大於sqrt（n）。

對於排序的順序打印的數字：

期間在範圍[1，SQRT（N）]打印僅在範圍除數[1，SQRT（N）]可以使用的陣列/矢量找到除數存儲範圍[sqrt（n），n]中的數字並在for循環結束後將其打印出來。下面是一個示例代碼

vector<int> otherNums; 
for(i=1;i*i<n;i++) { 
    if(num%i==0){ 
     cout<<i<<endl; 
     otherNums.push_back(n/i); 
    } 
} 
if(i*i == n) otherNums.push_back(i); 
for(i=(int)v.size() - 1 ;i>=0;i--) 
    cout<<otherNums[i]<<endl;

來源

2017-02-23 23:49:13

使用theta（n）效率打印除數

回答

相關問題