Detailed Explanation using Sieve
Intuition\n First, count all the primes from 1 to n using Sieve. Remember to terminate the outer loop at sqrt(n).\n Next , iterate over each positon and get the
# Intuition\n* First, count all the primes from 1 to **n** using **Sieve**. Remember to terminate the outer loop at **sqrt(n)**.\n* Next , iterate over each positon and get the count of prime positions, call it `k`.\n* So, for the `k` prime numbers, we have limited choice, we need to arrange them in `k` prime spots.\n* For the `n-k` non prime numbers, we also have limited choice. We need to arrange them in `n-k` non prime spots.\n* Both the events are indepent, so the total ways would be product of them.\n* Number of ways to arrange `k` objects in `k` boxes is `k!`.\n* Use the property that `(a*b) %m = ( (a%m) * (b%m) ) % m`.\n\n```\nclass Solution\n{\npublic:\n    int numPrimeArrangements(int n);\n};\n\nint Solution :: numPrimeArrangements(int n)\n{\n    vector<bool> prime(n + 1, true);\n    prime[0] = false;\n    prime[1] = false;\n    \n    for(int i = 2; i <= sqrt(n); i++)\n    {\n        if(prime[i])\n            for(int factor = 2; factor*i <= n; factor++)\n                prime[factor*i] = false;\n    }\n    \n    int primeIndices = 0;\n    for(int i = 1; i <= n; i++)\n        if(prime[i])\n            primeIndices++;\n    \n    int mod = 1e9 + 7, res = 1;\n\t\n    for(int i = 1; i <= primeIndices; i++)\n        res = (1LL*res*i) % mod;\n    for(int i = 1; i<= (n-primeIndices); i++)\n        res = (1LL*res*i) % mod;\n    \n    return res;\n    \n}\n```
[]