Permutation of first N positive integers such that prime numbers are at prime indices | Set 2
Given an integer N, the task is to find the number of permutations of first N positive integers such that prime numbers are at prime indices (for 1-based indexing).
Note: Since, the number of ways may be very large, return the answer modulo 109 + 7.
Examples:
Input: N = 3
Output: 2
Explanation:
Possible permutation of first 3 positive integers, such that prime numbers are at prime indices are: {1, 2, 3}, {1, 3, 2}
Input: N = 5
Output: 12
Approach: Using Sieve of Eratosthenes
- First, count all the primes between 1 to N using Sieve of Eratosthenes.
- Next, iterate over each position and get the count of prime positions, call it k.
- So, for the k prime numbers, we have limited choice, we need to arrange them in k prime spots.
- For the n-k non-prime numbers, we also have limited choice. We need to arrange them in n-k non-prime spots.
- Both the events are independent, so the total ways would be the product of them.
- Number of ways to arrange k objects in k boxes is k!
Below is the implementation of the above approach:
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> |
Output:
12
Time Complexity: O(N * log(log(N)))
Auxiliary Space: O(N)
Contact Us