Encuentre el número de permutaciones de los primeros N enteros positivos tales que la suma de dos números consecutivos cualesquiera sea primo donde todas las permutaciones cíclicas se consideran iguales.
Nota: La suma del primer y último elemento también debe ser primo.
Ejemplo :
Entrada: N = 6
Salida: 2
Explicación: Las dos permutaciones válidas son {1, 4, 3, 2, 5, 6} y {1, 6, 5, 2, 3, 4}. La permutación como {3, 2, 5, 6, 1, 4} se considera una permutación cíclica de la primera y, por lo tanto, no está incluida.Entrada : N = 3
Salida : 0
Explicación : No existen permutaciones válidas.
Enfoque : El problema dado se puede resolver usando recursividad y retroceso . Se puede observar que para encontrar el número distinto de ciclos, sin pérdida de generalidad, el ciclo debe comenzar con 1 . Se puede crear una array isPrime[] usando el Tamiz de Eratóstenes que almacena si un número es primo o no. Por lo tanto, cree una función recursiva y agregue elementos en la permutación de modo que su suma con el último elemento sea primo. Incrementa el conteo de permutaciones si la suma del primer y último elemento también es primo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Initialize a global variable N
const int maxn = 100;
// Stores the final count of permutations
ll ans = 0;
// Stores whether the integer is prime
bool isPrime[maxn];
bool marked[maxn];
void SieveOfEratosthenes(int n)
{
memset(isPrime, true, sizeof(isPrime));
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of P
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to find the number of valid permutations
void countCycles(int m, int n, int prev, int par)
{
// If a complete permutation is formed
if (!m) {
if (isPrime[prev + 1]) {
// If the sum of 1st and last element
// of the current permutation is prime
ans++;
}
return;
}
// Iterate from par to N
for (int i = 1 + par; i <= n; i++) {
if (!marked[i] && isPrime[i + prev]) {
// Visit the current number
marked[i] = true;
// Recursive Call
countCycles(m - 1, n, i, 1 - par);
// Backtrack
marked[i] = false;
}
}
}
int countPermutations(int N)
{
// Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N);
// Initializing all values in marked as 0
memset(marked, false, sizeof(marked));
// Initial condition
marked[1] = true;
countCycles(N - 1, N, 1, 1);
// Return Answer
return ans;
}
// Driver code
int main()
{
int N = 6;
cout << countPermutations(N);
return 0;
}
Java
// Java implementation for the above approach
import java.util.*;
class GFG{
// Initialize a global variable N
static int maxn = 100;
// Stores the final count of permutations
static int ans = 0;
// Stores whether the integer is prime
static boolean []isPrime = new boolean[maxn];
static boolean []marked = new boolean[maxn];
static void SieveOfEratosthenes(int n)
{
for (int i = 0; i <isPrime.length; i += 1) {
isPrime[i]=true;
}
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of P
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to find the number of valid permutations
static void countCycles(int m, int n, int prev, int par)
{
// If a complete permutation is formed
if (m==0) {
if (isPrime[prev + 1]) {
// If the sum of 1st and last element
// of the current permutation is prime
ans++;
}
return;
}
// Iterate from par to N
for (int i = 1 + par; i <= n; i++) {
if (!marked[i] && isPrime[i + prev]) {
// Visit the current number
marked[i] = true;
// Recursive Call
countCycles(m - 1, n, i, 1 - par);
// Backtrack
marked[i] = false;
}
}
}
static int countPermutations(int N)
{
// Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N);
// Initializing all values in marked as 0
for (int i = 0; i <marked.length; i += 1) {
marked[i]=false;
}
// Initial condition
marked[1] = true;
countCycles(N - 1, N, 1, 1);
// Return Answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 6;
System.out.print(countPermutations(N));
}
}
// This code is contributed by 29AjayKumar
Python3
# python implementation for the above approach import math # Initialize a global variable N maxn = 100 # Stores the final count of permutations ans = 0 # Stores whether the integer is prime isPrime = [True for _ in range(maxn)] marked = [False for _ in range(maxn)] def SieveOfEratosthenes(n): global ans global isPrime global marked for p in range(2, int(math.sqrt(n))+1): # If prime[p] is not changed, # then it is a prime if (isPrime[p] == True): # Update all multiples of P for i in range(p*p, n+1, p): isPrime[i] = False # Function to find the number of valid permutations def countCycles(m, n, prev, par): global ans global isPrime global marked # If a complete permutation is formed if (not m): if (isPrime[prev + 1]): # If the sum of 1st and last element # of the current permutation is prime ans += 1 return # Iterate from par to N for i in range(1+par, n+1): if (not marked[i] and isPrime[i + prev]): # Visit the current number marked[i] = True # Recursive Call countCycles(m - 1, n, i, 1 - par) # Backtrack marked[i] = False def countPermutations(N): global ans global isPrime global marked # Finding all prime numbers upto 2 * N SieveOfEratosthenes(2 * N) # Initial condition marked[1] = True countCycles(N - 1, N, 1, 1) # Return Answer return ans # Driver code if __name__ == "__main__": N = 6 print(countPermutations(N)) # This code is contributed by rakeshsahni
C#
// C# implementation for the above approach
using System;
public class GFG
{
// Initialize a global variable N
static int maxn = 100;
// Stores the final count of permutations
static int ans = 0;
// Stores whether the integer is prime
static bool []isPrime = new bool[maxn];
static bool []marked = new bool[maxn];
static void SieveOfEratosthenes(int n)
{
for (int i = 0; i < isPrime.Length; i += 1) {
isPrime[i] = true;
}
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of P
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to find the number of valid permutations
static void countCycles(int m, int n, int prev, int par)
{
// If a complete permutation is formed
if (m==0) {
if (isPrime[prev + 1]) {
// If the sum of 1st and last element
// of the current permutation is prime
ans++;
}
return;
}
// Iterate from par to N
for (int i = 1 + par; i <= n; i++) {
if (!marked[i] && isPrime[i + prev]) {
// Visit the current number
marked[i] = true;
// Recursive Call
countCycles(m - 1, n, i, 1 - par);
// Backtrack
marked[i] = false;
}
}
}
static int countPermutations(int N)
{
// Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N);
// Initializing all values in marked as 0
for (int i = 0; i <marked.Length; i += 1) {
marked[i] = false;
}
// Initial condition
marked[1] = true;
countCycles(N - 1, N, 1, 1);
// Return Answer
return ans;
}
// Driver code
public static void Main(string[] args)
{
int N = 6;
Console.WriteLine(countPermutations(N));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript implementation for the above approach
// Initialize a global variable N
const maxn = 100;
// Stores the final count of permutations
let ans = 0;
// Stores whether the integer is prime
let isPrime = new Array(maxn).fill(true);
let marked = new Array(maxn).fill(false);
function SieveOfEratosthenes(n) {
for (let p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of P
for (let i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to find the number of valid permutations
function countCycles(m, n, prev, par) {
// If a complete permutation is formed
if (!m) {
if (isPrime[prev + 1]) {
// If the sum of 1st and last element
// of the current permutation is prime
ans++;
}
return;
}
// Iterate from par to N
for (let i = 1 + par; i <= n; i++) {
if (!marked[i] && isPrime[i + prev]) {
// Visit the current number
marked[i] = true;
// Recursive Call
countCycles(m - 1, n, i, 1 - par);
// Backtrack
marked[i] = false;
}
}
}
function countPermutations(N)
{
// Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N);
// Initial condition
marked[1] = true;
countCycles(N - 1, N, 1, 1);
// Return Answer
return ans;
}
// Driver code
let N = 6;
document.write(countPermutations(N));
// This code is contributed by gfgking.
</script>
Producción
2
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prabaljainn y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA