[力扣] 算法 1175 (C#)

1175. 质数排列

public class Solution {
    const int MOD = 1_000_000_007;
    public int NumPrimeArrangements(int n)
    {
        var cnt = PrimeCount(n);
        var f = Factorial(Math.Max(cnt, n - cnt));
        return (int)(f[cnt] * f[n - cnt] % MOD);
    }

    int PrimeCount(int n)
    {
        var ba = new BitArray(n + 1);
        var ret = 0;
        for (var i = 2; i <= n; i++)
        {
            if (!ba[i])
            {
                ret++;
                for (var j = 2 * i; j <= n; j += i)
                    ba[j] = true;
            }
        }
        return ret;
    }

    long[] Factorial(int max)
    {
        var ret = new long[max + 1];
        ret[0] = 1;
        for (var i = 1; i < ret.Length; i++)
            ret[i] = ret[i - 1] * i % MOD;
        return ret;
    }
}

发表评论