1175. Prime Arrangements ---------E ~~~~~~~~

 

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

A:

1:  忘记了做permutation的时候，和数也可以做permutation的

2:  没有问。  n == 1时， 答案应该是1 还是0.  （我默认是0， 结果错了）

3：when res is of int type, its multiplication can suffer overflow. 

class Solution {
public:
    int numPrimeArrangements(int n) {
        vector<int> Prime{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};
        int nPrimes = 0;
        for(int i =0;i<Prime.size();i++){
            int val = Prime[i];
            if(val>n){
                break;
            }else{
                nPrimes ++;
            }
        }
        long res = 1;
        for(int i = 1; i<=nPrimes;i++){
            res = (res * i) % 1000000007;
        }
        for(int i = 1; i<=n-nPrimes;i++){
            res = (res * i) % 1000000007;
        }
        return (int)res;
    }
};