1175. Prime Arrangements

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

 

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.
Example 2:

Input: n = 100
Output: 682289015
 

Constraints:

1 <= n <= 100

这题还是有点意思的。首先题目让我们求排列组合的可能性。我们需要找出[1,N]之间所有的素数并且把它们放入质数的索引中，其余的放非素数，求有多少种可能性。

有多少个质数，那么就有多少个质数的索引，所以假设有N个质数，那么我们只需要求出它们的排列组合数量;其余的，我们再求出它们的排列素和数量，然后让它们相乘即可。

所以又变成了求某个范围内质数数量的题目。我们直接跑一个循环，首先可以排除非2的双数，它们肯定不是质数。然后当跑到另一半后退出循环即可，这个想想就可以理解，这样我们可以减少一半的循环。

class PrimeArrangements : public Solution {
public:
    void Exec() {
        auto res = numPrimeArrangements(11);
    }
    int numPrimeArrangements(int n) {
        int numOfPrime = 0;
        if (n >= 2) {
            ++numOfPrime;
        }

        for (int i = 3; i <= n; i++) {
            if (i % 2 == 0) {
                continue;
            }
            int flag = 0;
            for (int j = 3; j < i; j++) {
                if (j * j > i) {
                    break;
                }
                if (i % j == 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
                ++numOfPrime;
            }
        }

        long long permutations = 1;
        for (int i = 1; i <= numOfPrime; i++) {
            permutations *= i;
            permutations %= (long long)(1e9 + 7);
        }
        for (int i = 1; i <= n - numOfPrime; i++) {
            permutations *= i;
            permutations %= (long long)(1e9 + 7);
        }

        return int(permutations);
    }
};