Permutation of first N positive integers such that prime numbers are at prime indices | Set 2

Namachila November 19, 2025

0 0 5 minutes read

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 10⁹ + 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:

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 zambiatek!