Permutation of first N positive integers such that prime numbers are at prime indices | Set 2 | C ++ program to count permutations from 1 to N such that prime numbers occur at prime indices ;  ; Computing count of prime numbers using sieve ; Computing permutations for primes ; Computing permutations for non - primes ; Driver program
#include <bits/stdc++.h> NEW_LINE 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 ; 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 ; for ( int i = 1 ; i <= primeIndices ; i ++ ) res = ( 1LL * res * i ) % mod ; for ( int i = 1 ; i <= ( n - primeIndices ) ; i ++ ) res = ( 1LL * res * i ) % mod ; return res ; } int main ( ) { int N = 5 ; cout << numPrimeArrangements ( N ) ; return 0 ; }