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 programint 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 programpublic 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 indicesimport 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 indicesusing 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 codepublic 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 indicesvar 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 programvar 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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
