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

Question

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

我想通过(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] 满足 s[k] = true。

O(m)计算

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