algorithm - 计数小于 m 的数与 n 互质

Question

计数小于 m, m 的数与 n 互质

我想通过(phi(n)/n)*m来做这件事，但它总是有一些小错误。

一种方法可以使用包含-排除原则，但我正在寻找比这更好的算法。

例如

n = 20 m = 10
{1, 3, 7, 9}
Ans = 4

Answer 1

首先，您可以找到所有 x < m，其中 x 是质数且 x 是 n 的除数。它以 O(m * (x.count)) 计算

i = 1;

while x[i] not empty do  
{
    j = 1;

    while x[i] * j < m
    {
        s[(x[i] * j)] = false;
        j++; 
    }

    i++;
}

现在您可以找到所有 s[k] = true 的 s[k]。

它以 O(m) 计算

所以你可以在 O(m * (x.count)) 中完成所有步骤