algorithm - m より小さい n と互いに素な数を数える

Question

m, m より小さい n と互いに素な数を数える

(phi(n)/n)*mでこれを行うことを考えましたが、常に小さなエラーが発生します。

包含と排除の原則を使用する方法もありますが、それよりも優れたアルゴリズムを探しています。

例えば

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

Answer 1

まず、x が素数で x が n の約数であるすべての x < m を見つけることができます。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)) で実行できます