Pythonで解く素数の並べ替え問題：素数を素数インデックスに配置する順列の数

この記事では、1からnまでの数字を使った順列のうち、「素数が素数のインデックス位置（1始まり）に配置されている」ものの総数を求める問題を扱います。答えは非常に大きくなる可能性があるため、10⁹ + 7で割った余りを返します。

例えば n = 5 の場合、答えは12通りになります。有効な順列の一例は [1, 2, 5, 4, 3] です。一方、[5, 2, 3, 4, 1] は無効です。これは、素数である5がインデックス1（素数ではない）に置かれているためです。

解法のアプローチ

まず、getNum という補助メソッドを定義して n 以下の素数の個数を数えます。その後、素数の個数 x と非素数の個数 n − x それぞれについて階乗を計算し、掛け合わせることで答えを求めます。

• getNum メソッド： 2から100までの素数リストを用意し、リストを先頭から走査します。n より大きい素数が出現した時点でのカウント（＝ n 以下の素数の個数）を返します。
• メイン処理： x = getNum(n)、p = 1、m = 10⁹ + 7 とします。まず i を x から 1 まで減らしながら p *= i、p %= m を繰り返します。続いて i を n − x から 1 まで減らしながら同じ計算を行い、最終的な p を返します。

なぜこの方法で正しいのか

n 以下に素数が x 個あるとき、x 個の素数を x 個の素数インデックスへ配置する方法は x! 通りあります。同様に、残りの n − x 個の数（1と合成数）を n − x 個の非素数インデックスへ配置する方法は (n − x)! 通りあります。この2つの配置は互いに独立しているため、答えは x! × (n − x)! となります。毎回の剰余演算によって値の肥大化を防ぎ、オーバーフローなしに計算できます。

実装例

以下のPythonコードで実際の動作を確認できます。

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

n = 100 の場合、100以下の素数は25個存在するため、答えは 25! × 75! を 10⁹ + 7 で割った余りである 682289015 となります。