Python 中的素数排列

我们需要找到 1 到 n 的排列数，使得素数位于素数索引处。答案可能很大，返回答案模 10^9 + 7。因此，如果 n = 5，则输出将为 12。因此将有 12 个排列。一个可能的排列是 [1,2,5,4,3]，一个无效的排列是 [5,2,3,4,1]，因为 5 位于索引 1 处，这不是素数。

为了解决这个问题，我们将遵循以下步骤 -

  • 定义一个名为 getNum 的方法，如下所示 -
  • prime := 从 2 到 100 的所有素数的列表
  • 设置 i := 0
  • 当 i < prime 列表的长度时
    • 如果 prime[i] > n，则返回 i
    • i := i + 1
  • 返回 prime 的长度
  • 实际问题将按如下方式解决
  • x := getNum(n), p := 1, m := 10^9 + 7
  • 对于 i := x 到 0
    • p := p * i
    • p := p mod m
  • 对于 i := n – x 到 0
    • p := p * i
    • p := p mod m
  • 返回 p

示例

让我们看看以下实现以获得更好的理解 -

 在线演示

class Solution(object):
   def getNum(self,n):
      primes = [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]
      i = 0
      while i < len(primes):
         if primes[i]>n:
            return i
         i+=1
      return len(primes)
   def numPrimeArrangements(self, n):
      """
      :type n: int
      :rtype: int
      """
      x = self.getNum(n)
      p = 1
      m = 1000000000+7
      for i in range(x,0,-1):
         p*=i
         p%=m
      for i in range(n-x,0,-1):
         p*=i
         p%=m
      return p
ob1 = Solution()
print(ob1.numPrimeArrangements(100))

输入

100

输出

682289015

更新于: 2020年4月29日

267 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告