Dado un número entero N , la tarea es encontrar el número de permutaciones de los primeros N números enteros positivos tales que los números primos estén en índices primos (para la indexación basada en 1).
Nota: Dado que el número de vías puede ser muy grande, devuelva la respuesta módulo 10 9 + 7.
Ejemplos:
Entrada: N = 3
Salida: 2
Explicación:
Posible permutación de los primeros 3 enteros positivos, de modo que los números primos estén en índices primos: {1, 2, 3}, {1, 3, 2}
Entrada: N = 5
Salida: 12
Enfoque: uso de la criba de Eratóstenes
- Primero, cuente todos los números primos entre 1 y N usando el tamiz de Eratóstenes .
- A continuación, itere sobre cada posición y obtenga el recuento de posiciones principales, llámelo k.
- Entonces, para los k números primos, tenemos opciones limitadas, necesitamos ordenarlos en k lugares primos.
- Para los nk números no primos, también tenemos opciones limitadas. Necesitamos organizarlos en nk lugares no preferenciales.
- Ambos eventos son independientes, por lo que las formas totales serían el producto de ellos.
- ¡ El número de formas de organizar k objetos en k cajas es k!
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count
// permutations from 1 to N
// such that prime numbers
// occur at prime indices
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1e9 + 7;
int numPrimeArrangements(int n)
{
vector<bool> prime(n + 1, true);
prime[0] = false;
prime[1] = false;
// Computing count of prime
// numbers using sieve
for (int i = 2; i <= sqrt(n); i++) {
if (prime[i])
for (int factor = 2;
factor * i <= n;
factor++)
prime[factor * i] = false;
}
int primeIndices = 0;
for (int i = 1; i <= n; i++)
if (prime[i])
primeIndices++;
int mod = 1e9 + 7, res = 1;
// Computing permutations for primes
for (int i = 1; i <= primeIndices; i++)
res = (1LL * res * i) % mod;
// Computing permutations for non-primes
for (int i = 1; i <= (n - primeIndices); i++)
res = (1LL * res * i) % mod;
return res;
}
// Driver program
int main()
{
int N = 5;
cout << numPrimeArrangements(N);
return 0;
}
Java
// Java program to count
// permutations from 1 to N
// such that prime numbers
// occur at prime indices
import java.util.*;
class GFG{
static int MOD = (int) (1e9 + 7);
static int numPrimeArrangements(int n)
{
boolean []prime = new boolean[n + 1];
Arrays.fill(prime, true);
prime[0] = false;
prime[1] = false;
// Computing count of prime
// numbers using sieve
for (int i = 2; i <= Math.sqrt(n); i++) {
if (prime[i])
for (int factor = 2;
factor * i <= n;
factor++)
prime[factor * i] = false;
}
int primeIndices = 0;
for (int i = 1; i <= n; i++)
if (prime[i])
primeIndices++;
int mod = (int) (1e9 + 7), res = 1;
// Computing permutations for primes
for (int i = 1; i <= primeIndices; i++)
res = (int) ((1L * res * i) % mod);
// Computing permutations for non-primes
for (int i = 1; i <= (n - primeIndices); i++)
res = (int) ((1L * res * i) % mod);
return res;
}
// Driver program
public static void main(String[] args)
{
int N = 5;
System.out.print(numPrimeArrangements(N));
}
}
// This code contributed by sapnasingh4991
Python3
# Python3 program to count # permutations from 1 to N # such that prime numbers # occur at prime indices import math; def numPrimeArrangements(n): prime = [True for i in range(n + 1)] prime[0] = False prime[1] = False # Computing count of prime # numbers using sieve for i in range(2,int(math.sqrt(n)) + 1): if prime[i]: factor = 2 while factor * i <= n: prime[factor * i] = False factor += 1 primeIndices = 0 for i in range(1, n + 1): if prime[i]: primeIndices += 1 mod = 1000000007 res = 1 # Computing permutations for primes for i in range(1, primeIndices + 1): res = (res * i) % mod # Computing permutations for non-primes for i in range(1, n - primeIndices + 1): res = (res * i) % mod return res # Driver code if __name__=='__main__': N = 5 print(numPrimeArrangements(N)) # This code is contributed by rutvik_56
C#
// C# program to count permutations
// from 1 to N such that prime numbers
// occur at prime indices
using System;
class GFG{
//static int MOD = (int) (1e9 + 7);
static int numPrimeArrangements(int n)
{
bool []prime = new bool[n + 1];
for(int i = 0; i < prime.Length; i++)
prime[i] = true;
prime[0] = false;
prime[1] = false;
// Computing count of prime
// numbers using sieve
for(int i = 2; i <= Math.Sqrt(n); i++)
{
if (prime[i])
{
for(int factor = 2;
factor * i <= n;
factor++)
prime[factor * i] = false;
}
}
int primeIndices = 0;
for(int i = 1; i <= n; i++)
if (prime[i])
primeIndices++;
int mod = (int) (1e9 + 7), res = 1;
// Computing permutations for primes
for(int i = 1; i <= primeIndices; i++)
res = (int) ((1L * res * i) % mod);
// Computing permutations for non-primes
for(int i = 1; i <= (n - primeIndices); i++)
res = (int) ((1L * res * i) % mod);
return res;
}
// Driver code
public static void Main(String[] args)
{
int N = 5;
Console.Write(numPrimeArrangements(N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program to count
// permutations from 1 to N
// such that prime numbers
// occur at prime indices
var MOD = parseInt(1e9 + 7);
function numPrimeArrangements(n)
{
var prime = Array.from({length: n+1}, (_, i) => true);
prime[0] = false;
prime[1] = false;
// Computing count of prime
// numbers using sieve
for (var i = 2; i <= Math.sqrt(n); i++) {
if (prime[i])
for (factor = 2;
factor * i <= n;
factor++)
prime[factor * i] = false;
}
var primeIndices = 0;
for (var i = 1; i <= n; i++)
if (prime[i])
primeIndices++;
var mod = parseInt( (1e9 + 7)), res = 1;
// Computing permutations for primes
for (var i = 1; i <= primeIndices; i++)
res = ((1 * res * i) % mod);
// Computing permutations for non-primes
for (var i = 1; i <= (n - primeIndices); i++)
res = ((1 * res * i) % mod);
return res;
}
// Driver program
var N = 5;
document.write(numPrimeArrangements(N));
// This code contributed by shikhasingrajput
</script>
Producción:
12
Complejidad de tiempo: O(N * log(log(N)))
Espacio Auxiliar: O(N)