Concatenating and returning arrays in C++

Question

I am learning myself C++ by solving problems from the Euler project. One of the exercises were to find the maximum prime factor, which I found the fastest way to solve was to use divide and conquer, using the following code snippet:

long primeFactor1(long n);

long primeFactor(long n)
{
    long divisorR = findDivisor(n);
    long divisorL = n/divisorR;

    if (divisorR == n){
        return divisorR;
    }

    long primeFactorDivL = primeFactor1(divisorL);
    long primeFactorDivR = primeFactor1(divisorR);

    return std::max(primeFactorDivL,primeFactorDivR);
}

long primeFactor1(long n)
{
    std::cout << "Is "<<n<< " a prime? " << checkPrime(n) << std::endl;
    if (checkPrime(n)){
        return n;
    }
    else{
        return primeFactor(n);
    }
}

Where checkPrime is a function which checks it a number is a prime and findDivisor finds the smallest even divisor of a number n. So this program works nicely and gives and output instantly even for the number given in the problem (which was quite large, to say the least).

My problem is, however, I want to convert the program to return all the prime divisors instead of just the largest. Which means I basically have to change:

return std::max(primeFactorDivL,primeFactorDivR);

to something that concatenates the two instead and adjusts the functions such that they can return the array generated.

In Matlab which I come from I would just put square-brackets around s.t.

[primeFactorDivL,primeFactorDivR]

What is the best (preferably also easiest) way to do this in C++?

UPDATE:

I have tried implementing it using vectors, which can be seen in the code below using typecast at the leaves. However, trying to compile it I get the compilation error:

primeFactor.cpp:51:9: error: no viable conversion from 'typename
      enable_if<__is_forward_iterator<__wrap_iter<long *> >::value && is_constructible<value_type, typename
      iterator_traits<__wrap_iter<long *> >::reference>::value, iterator>::type' (aka
      'std::__1::__wrap_iter<long *>') to 'std::vector<long>'
  ...primeFactorDivL.insert( primeFactorDivL.end(), primeFactorDivR.begin(), primeFactorDivR.end() );
     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/bin/../include/c++/v1/vector:568:5: note: candidate constructor not
      viable: no known conversion from 'typename enable_if<__is_forward_iterator<__wrap_iter<long *>
      >::value && is_constructible<value_type, typename iterator_traits<__wrap_iter<long *>
      >::reference>::value, iterator>::type' (aka 'std::__1::__wrap_iter<long *>') to 'const
      std::__1::vector<long, std::__1::allocator<long> > &' for 1st argument
    vector(const vector& __x);
    ^
1 error generated.

Where my code is now:

std::vector<long> primeFactor1(long n);

std::vector<long> primeFactor(long n)
{
    long divisorR = findDivisor(n);
    long divisorL = n/divisorR;

    if (divisorR == n){
        return std::vector<long>(divisorR);
    }

    std::vector<long> primeFactorDivL( primeFactor1(divisorL) );
    std::vector<long> primeFactorDivR( primeFactor1(divisorR) );

    return primeFactorDivL.insert( primeFactorDivL.end(), primeFactorDivR.begin(), primeFactorDivR.end() );
}

std::vector<long> primeFactor1(long n)
{
    std::cout << "Is "<<n<< " a prime? " << checkPrime(n) << std::endl;
    if (checkPrime(n)){
        return std::vector<long>(n);
    }
    else{
        return primeFactor(n);
    }
}

WIth a `std::vector` you can create a vector of two numbers like just `{a, b}`. The interesting thing about this exercise is instead, I believe (but I haven't analyzed it, and it's late evening for me) to avoid O(n^2) behavior. And I think that essentially involves passing the result vector as a reference argument. Another possibility is to use a linked list (like `std::list`), but I think I'd go for the vector argument. Or you could re-express your algorithm as iterative. In that case pushing the items involves simply using `std::vector::push_back`. — Cheers and hth. - Alf, Jul 03 '16 at 21:10
You are not doing what your function states. You're supposed to return a `std::vector` in that function, but instead you're returning the value of `insert()`. You should just simply return `primeFactorDivL;` after you've done whatever needs to be done with it. — PaulMcKenzie, Jul 03 '16 at 21:36

score 3 · Accepted Answer · edited May 23 '17 at 11:58

3

Arrays in C++ have a fixed size, so you have to create a new one dynamically each time you concatenate and you have to remember to delete the old ones.

So I would suggest to just use vectors.

There is already a question on concatenating vectors and its done like this:

vector1.insert( vector1.end(), vector2.begin(), vector2.end() );

edited May 23 '17 at 11:58

Community

1
1

answered Jul 03 '16 at 20:37

Kevin Peña

712
3
10

In that case, how do I start the process? At the leaves, I return long integers, how to I combine those two into a vector? – Nicky Mattsson Jul 03 '16 at 20:58
Since the calls between `primeFactor()` and `primeFactor1()` are recursive you would need to change the type of the parameter and the return type of both functions to `std::vector`. Then change the logic in them to make their calculations based on the greater (or the last, depending on how you implement the insertion) element of the array they are receiving as parameters. You could also left the logic of your code alone, and keep a global array in which you push before returning from `primeFactor()` – Kevin Peña Jul 03 '16 at 21:11
I have tried to update it with given what you said, but now I receive the error shown above. – Nicky Mattsson Jul 03 '16 at 21:23

score 2 · Answer 2 · edited Jul 03 '16 at 20:58

2

There are multiple possibilities here. Since you are only interested in returning a pair of numbers, you could return a std::pair. You will need to

#include <utility>
change the return type of primeFactor to std::pair
change the return statement to return {primeFactorDivL, primeFactorDivR};

The last point relies on features of c++11, so you will have to make sure this is enabled for you compiler. In earlier C++ you could return std::make_pair(primeFactorDivL, primeFactorDivR) instead.

edited Jul 03 '16 at 20:58

VolAnd

6,367
3
25
43

answered Jul 03 '16 at 20:41

Spacemoose

3,856
1
27
48

I might misunderstand it, but I am not just returning a pair of numbers. I am creating a binary tree, where at the lowest level it is two numbers that are concatenated, but one level above I am concatenating two pairs of numbers, and so forth. – Nicky Mattsson Jul 03 '16 at 20:44
No, that's my bad -- I only looked at your bottom level. In that case I agree with Kevin Peña's answer – Spacemoose Jul 05 '16 at 08:15

Concatenating and returning arrays in C++

2 Answers2