5

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);
}
  • 2
    Are you doing only one split or as many splits as it takes? – candied_orange Oct 13 '16 at 16:18
  • Well I think that I'd have to split as many time as it takes, because the splitting can be uneven according to the example. – brajevicm Oct 13 '16 at 16:23
  • Uneven? Example? – candied_orange Oct 13 '16 at 16:33
  • 1
    @brajevicm To put CandiedOrange's question in another way, can you do splits such as "2|2|3" or can you split only once? – Vincent Savard Oct 13 '16 at 16:53
  • 2
    I think your question would be clearer if you further explained your potential solution. I personally don't understand what you mean by "convert an integer n to array", or how it could be used in a divide and conquer algorithm. To be honest, I don't see how your problem becomes more complex if you accept integers greater than 1000. Your problem seems to be easily solved by creating a function which returns all possible pairs, then iterating on those pairs and returning True if both numbers are prime. – Vincent Savard Oct 13 '16 at 19:35
3

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.

  • Re: the shortcut, are you talking about even length of the string of digits, or even number? If the latter, I don't understand your shortcut... since 22 is even but can be split as 2|2, and 2 is prime. If the former, I'm not sure, is there a relationship between prime numbers and their number of digits in base 10? Or have I completely misunderstood your shortcut? :) – Andres F. Oct 13 '16 at 21:35
  • 1
    Shortcut could be simplified to eliminating numbers ending in 4,6,8 or 0. – user949300 Oct 13 '16 at 22:00
  • I will try to implement this algorithm, thank you for helping me. I have one more question though. How would you split 672991 for example? – brajevicm Oct 13 '16 at 22:16
  • @brajevicm: [['6', '72991'], ['67', '2991], ['672', '991'], ['6729', '91'], ['67299', '1']? – DrakaSAN Oct 14 '16 at 9:34
  • @Andres - Thx, didn't think about the '22' case. I've updated my answer to reflect your comment as well as user949300's comment. – Jon Raynor Oct 14 '16 at 15:47
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.

  • 1
    Think of it this way: a prime number has exactly 2 divisors: 1 and itself. 1 has only 1 divisor, therefore it is not prime. (I personally find this definition easier to remember than the "normal" mathematical ones, which always have to add an explicit artificial rule "n >= 2".) – Jörg W Mittag Oct 13 '16 at 22:23
0

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.

  • Are you sure you're solving the OP's problem? I think by "split" he/she means splitting the string of digits into two strings, each of which represents a number which may or may not be prime (though I may have misunderstood the problem!). – Andres F. Oct 13 '16 at 19:03
  • You're probably right :-( – gnasher729 Oct 13 '16 at 20:52
0

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.