What is the main pattern in the Prime Arrangements problem?

The key pattern is arranging prime numbers at prime indices and non-primes at remaining positions, separating factorial counts for each group.

Why do we return the answer modulo 10^9 + 7?

Because the number of permutations grows quickly, modulo 10^9 + 7 keeps results within integer limits and prevents overflow.

How do I count primes efficiently for this problem?

Use a sieve of Eratosthenes or a direct primality check up to n to identify prime numbers without checking every permutation.

Can this approach handle n = 100?

Yes, counting primes and computing factorials modulo 10^9 + 7 scales efficiently up to n = 100, avoiding brute-force computation.

What are common mistakes to avoid in Prime Arrangements?

Common mistakes include misclassifying 1 as prime, neglecting modulo operations, and attempting full permutation generation instead of factorial multiplication.

#1175

Easy

auto_awesome数学·driven

LeetCode 题解工作台

质数排列

请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。由于答案可能会很大，所以请你返回答案模 mod 10^9 + …

数学

题目描述

请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。

让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。

由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。

示例 1：

输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。

示例 2：

输入：n = 100
输出：682289015

提示：

1 <= n <= 100

lightbulb

解题思路

方法一：数学

先统计 $[1,n]$ 范围内的质数个数，我们记为 $cnt$ 。然后求 $cnt$ 以及 $n-cnt$ 阶乘的乘积得到答案，注意取模操作。

这里我们用“埃氏筛”统计质数。

如果 $x$ 是质数，那么大于 $x$ 的 $x$ 的倍数 $2x$ , $3x$ ,… 一定不是质数，因此我们可以从这里入手。

设 $primes[i]$ 表示数 $i$ 是不是质数，如果是质数则为 $true$ ，否则为 $false$ 。

我们在 $[2,n]$ 范围内顺序遍历每个数 $i$ ，如果这个数为质数，质数个数增 $1$ ，然后将其所有的倍数 $j$ 都标记为合数（除了该质数本身），即 $primes[j]=false$ ，这样在运行结束的时候我们即能知道质数的个数。

时间复杂度 $O(n \times \log \log n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        def count(n):
            cnt = 0
            primes = [True] * (n + 1)
            for i in range(2, n + 1):
                if primes[i]:
                    cnt += 1
                    for j in range(i + i, n + 1, i):
                        primes[j] = False
            return cnt

        cnt = count(n)
        ans = factorial(cnt) * factorial(n - cnt)
        return ans % (10**9 + 7)

speed

复杂度分析

指标	值
时间	complexity is O(n log log n) using a sieve to count primes, plus O(n) for factorial computations. Space complexity is O(n) for the sieve and factorial storage. The dominant factor is prime counting and factorial computation.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate separates prime and composite numbers correctly.
question_mark
Observe whether modulo operations are applied to avoid overflow.
question_mark
Listen for explanations about factorial usage and arrangement counting.

warning

常见陷阱

外企场景

error
Attempting to generate all permutations, which is computationally infeasible.
error
Forgetting to apply modulo 10^9 + 7 during factorial multiplication.
error
Misidentifying prime numbers, especially 1, which is not prime.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute valid arrangements where primes occupy only even indices instead of prime indices.
arrow_right_alt
Find permutations for a given list of numbers instead of 1 to n following the prime arrangement pattern.
arrow_right_alt
Return the lexicographically smallest valid permutation instead of counting all permutations.

help

常见问题

外企场景

继续练习

#1185 一周中的第几天 #1154 一年中的第几天 #1201 丑数 III