LeetCode——1175.质数排列

通过万岁！！！

• 题目：找到1到n的所有素数（也就是质数），然后要求素数应该在素数的下标。然后非素数在非素数的下标。问有多少种排列组合情况，结果可能比较大，所以对10的9次方+7进行取模。素数就是除了自己以外，不能被其他的整数整除。
• 思路：找到小于等于n的素数的个数，求阶乘，然后乘非素数的阶乘即可。就是数学的排列组合。但是这里需要注意，我们需要用到long类型，不然会超出精度。
• 技巧：素数、阶乘

java代码

class Solution {
    public int numPrimeArrangements(int n) {
        // 首先找到有多少个质数
        int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
                89, 97, 101};// 必须多写一个
        int num = 0;// 多少个质数
        while (primes[num] <= n) {
            num++;
        }
        // 然后计算n-num的阶乘，然后*num的阶乘
        return (int) (factorial(n - num) * factorial(num) % 1000000007);
    }


    public long factorial(int n) {
        long ans = 1;
        for (int i = 2; i <= n; i++) {
            ans *= i;
            ans %= (Math.pow(10, 9) + 7);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 总结：题目不是很难，这里对素数就没有进行求解，而是直接罗列出来了。求解方式也很简单，网上有很多的。