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

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000007;
bool isPrime(int n)
{
    if (n <= 1)
        return false;
    for (int i = 2; i < n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

long long factorial(int n)
{
    if (n == 0 || n == 1)
        return 1;
    return (factorial(n - 1) % mod * n % mod) % mod;
}
int numPrimeArrangements(int n)
{
    int primeCount[n + 1];

    primeCount[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        if (isPrime(i))
        {
            primeCount[i] = primeCount[i - 1] + 1;
        }
        else
            primeCount[i] = primeCount[i - 1];
    }

    return (long long)factorial(primeCount[n]) % mod *
           factorial(n - primeCount[n]) % mod;
}

int main()
{

    int n = 5;
    cout << numPrimeArrangements(n) << "\n";

    return 0;
}