1.
Problem Statement
2.
Sample Test Cases
3.
Approach
4.
Code
4.1.
Input
4.2.
Output
5.
Complexities
5.1.
Time Complexity
5.2.
Space Complexity
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

# Count All Prime Numbers that Can be Formed using Digits of a Given Number

## Problem Statement

You have a string of size N containing digits. Count all the possible prime numbers formed using digits of the string S.

Let us remind you that a number is  prime if it is an integer greater than one and is not divisible by any positive integer other than one and itself.

## Sample Test Cases

``````Input: 12345
Output:  36
Explanation: Total 36 distinct prime numbers can be formed by using the digits '1', '2', '3', '4' and '5'. Some are 2, 3, 5, 23,....

Input: 22222
Output: 1
Explanation: Only one prime number can be formed, which is 2.``````

## Approach

The idea is to generate all the permutations using recursion and backtracking and checking each of them whether it satisfies the given constraint or not.

Steps To Solve

• Initialize a hashmap 'mp' to avoid duplicates.
• Declare a variable 'ans' to store the count.
• Make a function bool check(string &s) to check whether the number formed by the string s is valid or not.
• If the size of s is zero, return false.
• Convert string s to integer using the inbuilt stoi function and store the integer in num.
• If mp[num] == 1, it is already processed, return false. Else mark mp[num] as true.
• If num == 1, it is not a prime number, return false.
• If num == 2, it is a prime, return true.
• If num%2 == 0, it is not a prime, return false.
• As 2 is only the even prime, and we have already checked for that, iterate to all the odd numbers 'i' over a range [3, N^(1/2)] and check if i is a factor of num or not, if yes return false.
• If num passes all the above conditions, then it is a prime number that is not yet processed, so return true.
• Make a function void solve(string &s, string &curr, vector <bool> &vis, int &N) to generate all possible permutations.
• Check whether the current string 'curr' is valid or not by calling check(curr). If it returns true, increment the answer by 1.
•  Iterate over a range [0, N], using the variable i, and perform the following steps -
• Check whether the ith character of string is included in the current string curr or not (vis[i] == true or false).
• If vis[i] == false, mark it as true and push s[i] into curr.
• Recursively call the function solve(s, curr, vis, N).
• Backtrack to generate all the possible strings.
• Call the function solve by passing the parameters (s, curr, vis, N).

## Code

``````#include <bits/stdc++.h>
using namespace std;
const int M = 1e2 + 7;
//hashmap avoid duplicates
unordered_map <int, int> mp;
int ans;
//function to check whether the number formed by the string s is valid or not.
bool check(string &s){

//If the size of s is zero
if(s.size() == 0)
return false;
//Convert string s to integer
int num = stoi(s);
if(mp[num])
return false;
//mark num as processed
mp[num] = true;
//1 is not a prime
if(num == 1)
return false;
//2 is a prime number
if(num == 2)
return true;
//2 is a factor
if(num%2 == 0)
return false;
//iterate to all the odd numbers 'i' over a range [3, N^(1/2)] and check if i is a factor of num or not
for(int i = 3; i * i <= num; i += 2){
if(num%i == 0)
return false;
}
//num is a prime number
return true;
}
// function to generate all possible permutations
void solve(string &s, string &curr, vector <bool> &vis, int &N){
//check current string
if(check(curr)){
++ans;
}
for(int i = 0; i < N; ++i){
//Check whether the ith character of string s is included in the current string curr or not
if(vis[i])
continue;
//mark i visited
vis[i] = true;
//puch character s[i] to curr
curr.push_back(s[i]);
solve(s, curr, vis, N);
//backtrack
curr.pop_back();
vis[i] = false;
}
}
signed main(){
string s;
cin >> s;
int N = s.size();
vector <bool> vis(N, 0);
string curr = "";
//function call
solve(s, curr, vis, N);
cout << ans << "\n";
return 0;
}``````

#### Input

``12345``

#### Output

``36``

## Complexities

### Time Complexity

The time complexity is O(9^N)

### Space Complexity

The space complexity is O(N) (ignoring the stack frames).

## FAQs

1. What is Backtracking?
Backtracking is an algorithmic tool that recursively generates all the possible combinations to solve the given problem.

2. How do you check if a number is prime or not efficiently?
Checkout this coding ninjaâ€™s blog to get a better understanding.

## Key Takeaways

In this article, we solved a problem using recursion and backtracking. If you want to master competitive programming or prepare for coding interviews, then backtracking is one of the most important topics. Check out this coding ninjas' blog for getting a better hold on it.