1175. Prime Arrangements

The description of the problem

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.

 source ： Power button （LeetCode）
 link ：https://leetcode.cn/problems/prime-arrangements

an example

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.

 source ： Power button （LeetCode）

Notification

The overflow problem (mode and long to address this problem)

The codes for this

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
    
public:
    const int MOD = 1e9 + 7;
    int numPrimeArrangements(int n) {
    
        int primeNum = 0, res;
        primeNum = getPrimeNum(n);
        res = getRes(primeNum, n);
        return res;
    }
    int getPrimeNum(int n) {
    
        int primeNum = 0; 
        for (int i = 1; i <= n; i++) {
    
            if (isPrime(i)) {
    
                primeNum++;
            }
        }
        return primeNum;
    }
    bool isPrime(int n) {
    
        if (n == 1) {
    
            return false;
        }
        for (auto i = 2; i * i <= n; ++i) {
    
            if (n % i == 0) {
    
                return false;
            }
        }
        return true;
    }
    int getRes(int primeNum, int n) {
    
        long res = 1;
        for (int i = 1; i <= primeNum; i++) {
    
            res = (res * i) % MOD;
        }
        for (int i = 1; i <= n - primeNum; i++) {
    
            res = (res * i) % MOD;
        }
        return (int)res;
    }
};
int  main() {
    
    Solution s;
    long long unsigned int n = 5;
    cout << s.numPrimeArrangements(n) << endl;
    return 0;
}

The corresponding results

$ ./test
12