这是小川的第413次更新，第446篇原创
看题和准备
今天介绍的是LeetCode算法题中Easy级别的第264题（顺位题号是1175）。返回1到n的排列数，以使质数处于质数索引（索引从1开始）。（请记住，当且仅当整数大于1，并且不能将其写为两个均小于它的正整数的乘积，它才是质数。）由于答案可能很大，因此请以10^9 + 7为模返回答案。
例如：
输入：n = 5
输出：12
说明：[1,2,5,4,3]是有效的排列，但是[5,2,3,4,1]并不是，因为素数5在索引1处。
输入：n = 100
输出：682289015
注意：
- 1 <= n <= 100
解题
题目的意思是计算一个由1到n组成的数列中，质数恰好位于质数索引上的排列组合个数，本质上是一个数学问题。
结合n = 5的例子来看，1到5中，只有2,3,5是质数，1和4不是质数，因此排列质数就有3*2*1 = 6种可能，分别是:
[2,3,5],[2,5,3],[3,2,5],[3,5,2],[5,2,3],[5,3,2]
不是质数的1和4，只有两种可能，分别是
[1,4],[4,1]
因此，将质数和非质数组合起来，就是6*2 = 12种可能，分别是
[1,2,3,4,5],[1,2,5,4,3],[1,3,2,4,5],[1,3,5,4,2],[1,5,2,4,3],[1,5,3,4,2]
[4,2,3,1,5],[4,2,5,1,3],[4,3,2,1,5],[4,3,5,1,2],[4,5,2,1,3],[4,5,3,1,2]
因此，我们只需要计算出n中有多少个质数和非质数，再计算两者的阶乘即可，为了防止溢出，题目要求我们将计算结果对1000000007取余。
public int numPrimeArrangements(int n) {
int mod = 1000000007;
int primeNums = countPrime(n);
int nonPrimeNums = n - primeNums;
long result = 1;
for (int i=2; i<=primeNums; i++) {
result = (result*i)%mod;
}
for (int j=2; j<=nonPrimeNums; j++) {
result = (result*j)%mod;
}
return (int)result;
}
/**
* 计算1到n中，质数（只能被1和自身整除）的个数
* @param n
* @return
*/
public int countPrime(int n) {
if (n <= 1) {
return 0;
}
int count = 0;
for (int i = 2; i <= n; i++) {
boolean flag = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
count++;
}
}
return count;
}
小结
算法专题目前已更新LeetCode算法题文章270+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
