Splitting integer so that both sides are prime numbers

Question

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);
}

Answer 1

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.

Answer 2

My first thought was an approach coming from the opposite direction to @Jon Raynors. Not sure which is better, (i think his is probably faster) but here it is.

If the number has N digits, generate (or have pre-calculated) all the primes of less than N digits. Convert them all to strings. Then, organize them into arrays of arrays by length. e.g.

allPrimes[0] = [],
allPrimes[1] = ["1", "2", "3", "5", "7"];  // I forget, is 1 prime???

Then a loop (Javaish code here)

String testValue = String.valueOf(n);
int digits = testValue.length();

for (int i=1; i<digits; i++)
   for (String p1: allPrimes[i])
      for (String p2: allPrimes[digits-i])
         if (testValue.equals(p1+p2))
            return "matched for " + p1 + "|" + p2;

return "no match";

As others have noted, any number ending in 4,6,8 or 0 can be instantly eliminated.

Answer 3

Maths first: If n is odd then one number must be equal to 2, and n-2 must be prime. If n = 4 then n = 2 + 2. If n >= 6 is even then it would have to be the sum of an odd prime ≤ n/2 and an odd prime ≥ n/2.

Chances that a large odd number p is prime are about 2 / ln p. Create a sieve to find the primes from n - 5 (ln p)^2 to n - 1, then check if there is a prime p in that sieve where n - p is also prime. If you can't find one, make the sieve larger.

I haven't got the slightest clue how "divide and conquer" would come into this.

Answer 4

You are correct, an array is an effective method of getting started. How you end up doing it really boils down to your coding preference, but you'd probably want to start as follows.

Firstly you'd need a function to check whether or not an input is prime. How you code that is largely personal, usually it ends up being a loop with a modulus operator. I follow the functional programming paradigm, so my code would look something like this:

*Note: there are mathamatical algorithms that do this more efficiently, I just wrote this one because it's easy to reason about.

function isPrime(x, y = Math.floor(x/2)){
  // x is input. Anything greater than half of x can't be divided into it
  cleanly.

  /*if our starting value is less than 3, it's automatically not prime.
  if(x < 3){
    return false;
  }

  //Does y fit into x cleanly? Yes? Then it can't be prime.
  if(x % y === 0){
    return false;
  }

  /*We've counted y down to 2. 2 nor any of the numbers before it have fit
  into x, therefore x is prime.*/
  if(y <= 2){
    return true;
  }

  /*assuming nothing else fit, we're ready to try again. This time with y
  as a lower value*/
  return isPrime(x,y-1);
}

Now that we can easily check if a number is prime, all we have to do is run through out number.

Let's say our starting number is 1234. First we'd turn that into an array, [1,2,3,4]. Then we'd right another function to automatically concatenate our array as necessary and check primes. We'd do something like this:

split the array at the first position [1,2,3,4] becomes 1|234
  Is 1 prime?
    Yes: is 234 Prime?
      Yes: return "These numbers can be split.";
      No: next step;
    No: next step;

split the array at the second position [1,2,3,4] becomes 12|34
  Is 12 prime?
    Yes: is 34 Prime?
      Yes: return "These numbers can be split.";
      No: next step;
    No: next step;

split the array at the second position [1,2,3,4] becomes 123|4
  Is 123 prime?
    Yes: is 4 Prime?
      Yes: return "These numbers can be split."
      No: next step;
    No: return "These numbers can't be split.";

You would run something like this in a loop that runs itself a number of times equal to 1 less then the length of the array (because the |1234 and 1234| splits are meaningless). As far as concatenations and working with the arrays go, that's a subject for another time. In general, it varies slightly from language to language.

Answer 5

If the number doesn't end in 1, 3, 7 or 9, then any number taken from the right of the string with two or more digits cannot be a prime, so you check whether the last digit is 2 or 5, and the first n-1 digits are a prime.

If the number ends in 1, 3, 7 or 9, then you try all combinations of k digits from the left and n-k digits from the right, for 1 ≤ k ≤ n-1 in the order k = 1, n-1, 2, n-2, 3, n-3 etc. because that way, you tend to have one small number that is easier checked for primality.

The obvious way would be to check that the left number is a prime, then to check that the right number is a prime, or in the opposite order. However, that is quite inefficient if you have a 30 digit prime and an 70 digit number divisible by 7, for example.

Instead, you check for some range of small primes p if either number is divisible by p - that improves your chances to prove quickly that one number is not prime. Once you tested enough trial divisors, you use the Miller-Rabin test alternating between both numbers to prove one is composite. If that fails, you go for a primality test for both numbers.

Note that if you have random numbers, it is much more likely that they are composite, and highly likely that at least one of two is composite, so the execution time won't be too bad - unless the number can be split because then you will have to prove that two numbers of which at least one is large are both primes.