使用θ(N)效率排序的打印除法
使用θ(N)效率排序的打印除法
提问于 2017-02-23 14:37:16
我很难正确地实现这一点。我希望创建一个函数，该函数确定用户输入userNum的所有除数，并将它们输出给用户。当userNum = 16时，我得到了输出1，16，2，8，我没想到顺序是正确的，但我遗漏了4，并且很难弄清楚原因。有什么想法吗？我试着用θ(sqrt(Num))效率来做这个。
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;
}
}更新:我已经打印了所有的数字，但仍然试图确定如何按顺序打印它们，同时保持在to (N)效率内。
回答 4
Stack Overflow用户
发布于 2017-02-23 15:04:59
- 将循环终止条件操作更改为
<=，现在您将看到4。 - 摆脱
sqrt函数调用。最好使用这个循环 (divisorCounter = 1；divisorCounter * divisorCounter <= num；divisorCounter++)
Stack Overflow用户
发布于 2017-02-23 14:42:52
一定要仔细检查你的边缘条件。
- 什么是
sqrt(num)？ - 在
divisorCounter循环中通过测试的最大的for是什么？ 4会通过测试吗？
我认为，如果你仔细观察这一行，记住这三个问题，你就会消除这个错误。
Stack Overflow用户
发布于 2017-02-23 15:49:13
使其在sqrt(n)时间复杂度中运行的：
对于任意n= any，无论是a<=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;页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42427513
复制
相似问题
存储用户信息的最佳实践
返回用户信息的最佳实践
用户身份验证最佳实践
存储Facebook用户信息最佳实践？
在Redis中存储用户信息的最佳实践
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
