我怎样才能加快我的算法？

Question

我正在解决一些问题，但我无法解决这些问题。我必须编写一个用户输入十进制数的代码，并且我需要计算该数字在其他众多系统中以数字 1 开头的次数。这是算法：

for (int i = 3; i <= n; i++) {
    int z = n;
    while (z != 0) {
        x = z % i;
        z = z / i;
    }
    if (x == 1) {
        brOsnova++;
    }
}

Answer 1

不用循环，使用这个：

x = x - ((x / i) * i);
if (x == 1)
{
    ...
}

这仅适用于整数数学。

Answer 2

您可以通过不检查验证的 i 来加速它

i <= n < 2*i 因为他们都会满足。因此，只检查for(int i = 3; i <= n/2; ++i)，然后将(n+1)/2添加到最后的brOsnova.

我相信它可以进一步加速并且必须有一些 O(log(n)) 算法，但也许它会很牵强......或者 algorithm 标签的一个很好的候选问题.

我怎样才能加快我的算法？

How I can speed up my algorithm?

c++

algorithm

base