[假设您有一个程序one_factor(N)，给定一个n位二进制数字N，它在Theta(n^2)时间返回该数字的质数之一（请注意，我使用了小写的n以我的theta表示法。）
[使用该算法，我想找到一种有效的算法来将n位二进制数分解为质数并打印出质因数。此外，我想知道算法作为n的函数运行的速度，并且还想计算我的算法在最坏情况下作为one_factor(N)的函数使用n oracle的近似次数。
假设两个Theta(n)位二进制数相加/相除/相乘/相减需要n时间。
这里是一种有效的算法：
one_factor(N)。如果函数返回N，则N为质数，我们就完成了。否则，请分割此主要因素并将其存储在某处。重复此过程，直到完成。现在，我无法根据n分析此过程的运行时。为简单起见，如果N是2的幂，则n = log_2(N)，但我不太确定如何从此处继续。
我不知道如何找到我们称为one_factor的最坏情况的次数，并且我也无法分析最坏情况的运行时间。
首先，甲骨文很棒但很慢。因此，您想先尝试进行庭审。
从Arithmetic functions in Wikipedia开始，如果您使用牛顿-拉夫森除法和Harvey-Hoeven算法，则可以在时间p内检查是否可以被素数O(n log(n))整除。用Eratosthenesesin筛分时间远小于O(n / log(n))来计算n素数到O(n^2)的可能性。可以按时间O(n^2)进行试算。 （使用更实用的乘法算法，您可以在更差的时间内完成操作。这不会对总体结果产生影响。）
现在您指的是甲骨文。每个预言片都花费时间O(n^2)，与之相比，除法很小。它将数字的大小减少至少n倍。需要如何划分？ O(log_n(2^n)) = O(log(2^n)/log(n)) = O(n/log(n))。根据上述相同算法，每个除法为O(n log(n))。
结果算法为O(n^2 * (n * log(n)) * n/log(n)) = O(n^4)。请注意，/log(n)是在必须咨询Oracle之前进行试算而节省的资金。
[请注意，您无法通过执行更多的除法运算来改善此情况，因为如果尝试遍历n^2的所有素数，则比原始算法和oracle除法的big-O花费的时间更多。部分仍然相同。
注意，除数后，您的N变为N / 2或更小。因此，您最多需要log2（N）个oracle调用。这是O（n）。每次调用花费的时间为O（n²）或更短（根据您对O的定义，可能需要提及“较少”）。
如果您的N为2的幂，则将导致最坏的调用次数。幸运的是，它还实现了每次调用时执行时间的最坏情况，因为在它们的前半部分，该数字足够大-它至少具有n / 2位数字。