leetcode算法第105题（LeetCode基础算法题第163篇）

技术提高是一个循序渐进的过程，所以我讲的leetcode算法题从最简单的level开始写的，然后到中级难度，最后到hard难度全部完。目前我选择C语言，Python和Java作为实现语言，因为这三种语言还是比较典型的。由于篇幅和精力有限，其他语言的实现有兴趣的朋友请自己尝试。

如果有任何问题可以在文章后评论或者私信给我。

如果有朋友希望我讲些其他话题，请在评论区留言或者私信给我。

持续分享，敬请关注。

LeetCode 1175. 质数排列（Prime Arrangements）

问题描述：

返回数字[1, n]的排列数，使得，质数在质数索引上（索引从1开始）(一个整数是质数是指，当且仅当它大于1，并且不能写成两个小于它的正整数的乘积。)因为排列数可能非常的大，所以请将排列数与1000000007的模作为结果返回。

注:

1 <= n <= 100；

示例：

C语言实现：

这道题实际上就是一个关于排列组合的数学问题。

首先，如果n给定，那么区间[1,n]内的质数和非质数就都确定了。

关于质数的问题，题目对n做了限制，n最大为100，所以我个人认为不用实现算法来找质数，100以内的质数只有25个，我们可以直接写出来：

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

为了减少查找开销，我的实现牺牲一点存储空间。我们定义一个长度是101的数组arr，对于每个arr[i]，表示的是[0,i]间的所有质数的个数。这样我们就可以通过arr[n]知道，区间[1,n]间有多少个质数了。

然后我们开始计算排列数。我们将之分成两个步骤：

1. 假设有a个质数，那么这a个质数就有相应的a个质数下标与之对应，则，将这a个质数放入a个质数下标中就有a!中不同的顺序；
2. 同样的存在n-a个非质数，有n-a个下标与之对应，那么放置它们有(n-a)!种不同的顺序；

显然以上两个步骤是要同时发生的，所以总的排列数是：a!*(n-a)!。

剩下的就是关于这个结果的计算。

随着n的取值递增，这个数会迅速变的非常大。对于计算阶层的每一个乘法步骤，都有可能会导致数值溢出。所以我们除了按照题目的要求在每步乘法步骤中做模运算以外，我们还要首先将返回变量的类型设置为long，因为取模是在乘法运算出结果后再进行的，所以不能让乘法运算出现数值溢出问题。

详细代码如下:

Java语言实现：

Java 的实现和C语言的实现一致，不再撰述。

代码如下：

Python语言实现：

Python 的实现和C语言的实现一致，不再撰述。

代码如下：

---

,