Construct the Cypher string based on the given conditions
Tags: algorithms, cpp, cryptography
Published: 2021-02-13 12:46:51

Given a number N, the task is to convert the given number into a Cypher string on the basis of below conditions:  

- If N is a semiprime, then change every digit at even places of N to it’s corresponding matched alphabet as shown below.
- If N can be written as a sum of two primes, then change every digit at odd places of N to it’s corresponding matched alphabet as shown below.
- If both the condition satisfy the concatenate the above two strings formed.
- If N can’t satisfy the above three criteria, then print “-1”.
Below is the list of matched character:  

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/2n7q2np7ef4yd1lzltmj.png)

**Examples:** 

> **Input**: N = 61 
**Output**: 6B 
**Explanation**: 
Since 61 can be expressed as a sum of two primes: 61 = 2 + 59 
Therefore, the resultant string after changing the character at even index is “6B”.
> **Input**: N = 1011243 
**Output**: B0B1C4D 
**Explanation**: 
Since 1011243 is Semiprime number: 1011243 = 3 * 337081 
Therefore, the resultant string after change the character at even index is “B0B1C4D”. 

**Approach:**  

- Check if the given number N is semi prime or not by using the approach discussed in this article. If yes, then do the following: 
 - Convert the given number N to string(say str) using to_string() function.
 - Traverse the above string formed and changed the characters at even index as:
```
str[i] = char((str[i] - '0') + 65)
```
 - Print the new string formed.
 - Check if the given number N can be expressed as a sum of two prime numbers or not using the approach discussed in this article. If yes, then do the following: 
  - Convert the given number N to string(say str) using to_string() function.
  - Traverse the above string formed and changed the characters at odd index as:
```
str[i] = char((str[i] - '0') + 65)
```
 - Print the new string formed.
 - If the above two condition doesn’t satisfy then we can’t form Cypher String. Print “-1”.

Below is the implementation of the above approach:
```cpp
// C++ program for the above approach
 
#include "bits/stdc++.h"
using namespace std;
 
// Function to check whether a number
// is prime or not
bool isPrime(int n)
{
    if (n <= 1)
        return false;
 
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return false;
    }
 
    return true;
}
 
// Function to check if a prime number
// can be expressed as sum of
// two Prime Numbers
bool isPossibleSum(int N)
{
    // If the N && (N-2) is Prime
    if (isPrime(N)
        && isPrime(N - 2)) {
        return true;
    }
    else {
        return false;
    }
}
 
// Function to check semiPrime
bool checkSemiprime(int num)
{
    int cnt = 0;
 
    // Loop from 2 to sqrt(num)
    for (int i = 2; cnt < 2
                    && i * i <= num;
         ++i) {
        while (num % i == 0) {
            num /= i,
 
                // Increment the count of
                // prime numbers
                ++cnt;
        }
    }
 
    // If num is greater than 1, then
    // add 1 to it
    if (num > 1) {
        ++cnt;
    }
 
    // Return '1' if count is 2 else
    // return '0'
    return cnt == 2;
}
 
// Function to make the Cypher string
void makeCypherString(int N)
{
 
    // Resultant string
    string semiPrime = "";
    string sumOfPrime = "";
 
    // Make string for the number N
    string str = to_string(N);
 
    // Check for semiPrime
    if (checkSemiprime(N)) {
 
        // Traverse to make Cypher string
        for (int i = 0; str[i]; i++) {
 
            // If index is odd add the
            // current character
            if (i & 1) {
                semiPrime += str[i];
            }
 
            // Else current character is
            // changed
            else {
                semiPrime
                    += char(
                        str[i] - '0' + 65);
            }
        }
    }
 
    // Check for sum of two primes
    if (isPossibleSum(N)) {
 
        // Traverse to make Cypher string
        for (int i = 0; str[i]; i++) {
 
            // If index is odd then
            // current character is
            // changed
            if (i & 1) {
                sumOfPrime
                    += char(
                        str[i] - '0' + 65);
            }
 
            // Else add the current
            // character
            else {
                sumOfPrime += str[i];
            }
        }
    }
 
    // If the resultant string is ""
    // then print -1
    if (semiPrime + sumOfPrime == "") {
        cout << "-1";
    }
 
    // Else print the resultant string
    else {
        cout << semiPrime + sumOfPrime;
    }
}
 
// Driver Code
int main()
{
 
    // Given Number
    int N = 1011243;
 
    // Function Call
    makeCypherString(N);
 
    return 0;
}
```
**Output:** 
```
B0B1C4D
```