# 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`

``````class Solution {
public:
int numPrimeArrangements(int n) {
long res = 1, cnt = 1, M = 1e9 + 7;
for (int i = 3; i <= n; i += 2) {
bool pass = true;
for (int factor = 3; factor * factor <= i; factor += 2) {
if (i % factor == 0) {
pass = false;
break;
}
}
if (pass) ++cnt;
}
for (int i = 1; i <= cnt; ++i) {
res = res * i % M;
}
for (int i = 1; i <= n - cnt; ++i) {
res = res * i % M;
}
return res;
}
};
``````

``````class Solution {
public:
int numPrimeArrangements(int n) {
long res = 1, cnt = 0, M = 1e9 + 7;
vector<bool> prime(n + 1, true);
prime[0] = false; prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (prime[i]) {
for (int factor = 2; factor * i <= n; ++factor) {
prime[factor * i] = false;
}
}
}
for (int i = 1; i <= n; ++i) {
if (prime[i]) ++cnt;
}
for (int i = 1; i <= cnt; ++i) {
res = res * i % M;
}
for (int i = 1; i <= n - cnt; ++i) {
res = res * i % M;
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1175

Count Primes

https://leetcode.com/problems/prime-arrangements/

https://leetcode.com/problems/prime-arrangements/discuss/371968/Detailed-Explanation-using-Sieve

https://leetcode.com/problems/prime-arrangements/discuss/371862/JavaPython-3-two-codes-each-count-only-primes-then-compute-factorials-for-both-w-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation