Algorithms – Splitting Integers into Prime Numbers

algorithms

The problem

You're given an n number. Check if that n number can be splitted in half so that both sides of a | are prime numbers.

Example:

Input Output

223   2|23
123   Not possible to split.

My Idea

I was given an example of n number that has only three digits, and in that case it would be easy to finish the task, but it wasn't stated that n number is going to be three digits so that makes the problem much more complex, in my opinion.

So if n could have m number of digits I'd do the next. Convert an integer n to array and then implement some sort of a divide and conquer algorithm. However, I'm not sure how am I going to compare each element to the rest of the element(s).

Does anyone have any ideas how can I complete the algorithm? Also nothing is set in stone so any other suggestions would be more than welcome.

Update

Thanks to everyone I finished the algorithm. I will post my code below.

#include <iostream>
#include <cmath>

using namespace std;

int numberOfDigits(int n)
{
    int digits = 0;
    if(n < 0)
        digits = 1;
    while(n)
    {
        n /= 10;
        digits++;
    }
    return digits;
}

bool isPrime(int n)
{
    int isPrime = true;
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
        {
            isPrime = false;
            break;
        }
    }

    if(isPrime && n > 1)
        return true;
    else
        return false;
}

int removeLastDigits(int n, int count)
{       
    return n / pow(10, count);
}

int getLastDigits(int n, int count)
{       
    return n % (int)pow(10, count);
}

void findPair(int n, int m)
{
    int a = n;
    int b = m;
    int counter = 1;
    int digits = numberOfDigits(n);
    int arePrimes = 0;

    while(digits >= 1)
    {
        if(isPrime(a) && isPrime(b))
        {
            cout << a <<"|" << b << endl;
            arePrimes = 1;
            break;
        }
        else
        {
            a = removeLastDigits(n, counter);
            b = getLastDigits(n, counter);
            counter++;
            digits--;
        }
    }


    if(arePrimes == 0)
        cout << "Not possible to split." << endl;
}

int main()
{
    int n;
    cout << "Enter the number: ";
    cin >> n;
    findPair(n, 0);
}

Best Answer

First create the list of numbers to check based on the initial number.

Example: 253

Assume split only once.

The Numbers From the initial number: [2,53], [25,3]

Note, one could do some de-duping here as well to avoid double processing the same number (Example: 111 only has two numbers 1, 11).

Each of these "split pair" can be checked if each number is prime.

If (IsPrime(2) and IsPrime(53)) => then true
If (IsPrime(25) and IsPrime(3)) => then false (25 is not prime)

So, just send each number to your IsPrime() number sieve. (Eratosthenes, etc.) In this case the numbers to check for prime are 2,53,25,3. Then "And Logic Gate" each split pair for the final answer. One could parallelize IsPrime() for multiple number processing at the same time.

There are some shortcuts. If the original number ends in 4,6,8, or zero, any "split pair" will always evaluate to false since one of the numbers in the pair is even and never prime. (@Andres F., @user949300) So, one could do that check first rather than running all the numbers through the sieve as a short circuit to save CPU. I'm sure there are some other tricks as well.

Related Topic