Условие

Верни количество перестановок чисел от 1 до n, при которых простые числа находятся на простых позициях. Результат верни по модулю 10^9 + 7.

Примеры

Input: n = 5 Output: 12 Explanation: Например, одна из корректных перестановок [1,2,5,4,3].

Input: n = 100 Output: 682289015

Решение

fun numPrimeArrangements(n: Int): Int {
    val MOD = 1_000_000_007

    // Функция считает количество простых чисел от 1 до n (Решето Эратосфена)
    fun countPrimes(n: Int): Int {
        val isPrime = BooleanArray(n + 1) { true }
        isPrime[0] = false
        isPrime[1] = false
        var count = 0
        for (i in 2..n) {
            if (isPrime[i]) {
                count++
                var j = i * 2
                while (j <= n) {
                    isPrime[j] = false  // вычёркиваем составные числа
                    j += i
                }
            }
        }
        return count
    }

    // Вычисляет факториал числа по модулю MOD
    fun factorial(num: Int): Long {
        var res = 1L
        for (i in 2..num) {
            res = (res * i) % MOD  // каждый раз берём модуль
        }
        return res
    }

    val primes = countPrimes(n)            // количество простых чисел
    val nonPrimes = n - primes             // количество непростых чисел
    // возвращаем произведение факториалов количества простых и непростых позиций по модулю
    return (factorial(primes) * factorial(nonPrimes) % MOD).toInt()
}

Временная сложность

O(n log log n), из-за подсчёта простых чисел.

Пространственная сложность

O(n), используется массив для решета.