2022-06-30

[Zheaoli]

2022-06-30

[SaraadKun]

1175. 质数排列

    long m = (long) 1e9 + 7;

    public int numPrimeArrangements(int n) {
        //计数小于等于n的质数cnt，ans = A(cnt, cnt) * A(n-cnt, n-cnt) % m; 注意取模时不要越界;
        int n1 = countPrime(n);
        return (int)(permutation(n1) * permutation(n - n1) % m);
    }

    int countPrime(int n) {
        int ans = 0;
        int[] prime = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (prime[i] == 0) {
                ans++;
                for (int j = i * i; j <= n; j += i) {
                    prime[j] = 1;
                }
            }
        }
        return ans;
    }

    long permutation(int n) {
        long ans = 1;
        while (n > 0) {
            ans = ans * n-- % m;
        }
        return ans;
    }

---

WeChat: Saraad

[thorseraq]

1175. 质数排列

class Solution {
    public int numPrimeArrangements(int n) {
        int mod = (int) (1e9 + 7);
        int primeCnt = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                primeCnt++;
            }
        }

        long res = 1;
        // primeCnt, n-primeCnt
        for (int i = primeCnt; i >= 2; i--) {
            res = (res * i) % mod;
        }
        for (int i = n - primeCnt; i >= 2; i--) {
            res = (res * i) % mod;
        }

        return (int) res;
    }

    private boolean isPrime(int x) {
        for (int i = 2; i <= (int) Math.sqrt(x); i++) {
            if (x % i == 0) {
                return false;
            }
        }

        return true;
    }
}