Efficient prime factorization for large numbers

I've been working on a little problem where I need to compute 18-digit numbers into their respective prime factorization. Everything compiles and it runs just fine, considering that it actually works, but I am looking to reduce the run time of the prime factorization. I have implemented recursion and threading but I think I might need some help in understanding possible algorithms for large number computation.

Every time I run this on the 4 numbers I have pre-made, it takes about 10 seconds. I would like to reduce this to possibly 0.06 seconds if there are any ideas out there.

I noticed a few algorithms like Sieve of Eratosthenes and producing a list of all the prime numbers prior to computing. I'm just wondering if someone could elaborate on it. For instance, I'm having issues understanding how to implement Sieve of Eratosthenes into my program or if it would even be a good idea. Any and all pointers on how to approach this better would be really helpful!

```
#include
#include
#include
#include

using namespace std;
using namespace std::chrono;

vector threads;
vector inputVector;
bool developer = false;
vector primeVector;

class PrimeNumber
{
long long initValue; // the number being prime factored
vector factors; // all of the factor values
public:
void setInitValue(long long n)
{
initValue = n;
}
void addToVector(long long m)
{
factors.push_back(m);
}
void setVector(vector m)
{
factors = m;
}
long long getInitValue()
{
return initValue;
}
vector getVector()
{
return factors;
}
};

vector primes;

// find primes recursively and have them returned in vectors
vector getPrimes(long long n, vector vec)
{
double sqrt_of_n = sqrt(n);

for (int i = 2; i > input;
if (input == 0)
{
break;
}
inputVector.push_back(input);
} while (input != 0);
}

int main()
{
vector temp1; // empty vector

Obviously, the best way to speed up your code woud be use another algorithm. However, the other posts already do a great job covering that part. Therefore, I will review the other things in your code that could have been done better:

-
It seems that you forgot to include the header ` for std::sqrt. Your implementation may include it from another header, but that's not guaranteed by the standard. My implementation produced a compile-time error because of the lack of .

-
threads.push_back(thread([&]{ / ... / })); is redundant: we already know that threads is a std::vector, so let's write threads.emplace_back([&]{ / ... / }); instead.

-
You have problems due to paralellism. When I try to run your program, I get an std::out_of_range exception thrown which says that I tried to access the nth element of a std::vector of size n. I did not understand all the details, but it comes from this loop:

for (int i = 0; i < inputVector.size(); i++)
{
    PrimeNumber prime;
    prime.setInitValue(inputVector.at(i));
    threads.emplace_back([&]{
        prime.setVector(result1 = getPrimes(inputVector.at(i), temp1));
        primes.push_back(prime);
    });
}

In this loop, the lambda captures all the variables by reference and that's a bad idea: once the thread is spawn, i might be incremented before inputVector.at(i) is called. To avoid this problem, you should take i by value in the capture instead of taking it by reference:

threads.emplace_back([&, i]{
    /* ... */
});

Capturing i by value ensures that it won't be modified by another thread meanwhile. In multithreaded code, it is really important to think about what should be taken by value and what should be taken by reference.

-
Moreover, on the same piece of code, you have concurrent stores on primes through the method push_back. While I didn't get any error - it seems that you didn't either -, this may be a data race. Therefore, you should use an std::mutex to lock primes before pushing values to it (that comment is also valid for result1):

std::mutex primes_mutex;
for (int i = 0; i  lock(primes_mutex);
        prime.setVector(result1 = getPrimes(inputVector.at(i), temp1));
        primes.push_back(prime);
    });
}

Note that I used a, std::lock_guard to guard the std::mutex. It avoids to forget a potential call to unlock since it invokes the unlocking function when its destructor is called.

-
I love to focus on small pieces of code, so there we go: the loop above can still be improved thanks to the C++11 range-based for loop:

std::mutex primes_mutex;
for (long long val: inputVector)
{
    PrimeNumber prime;
    prime.setInitValue(val);
    threads.emplace_back([&, val]{
        std::lock_guard lock(primes_mutex);
        prime.setVector(result1 = getPrimes(val, temp1));
        primes.push_back(prime);
    });
}

This iteration style allows to avoid the double concurrent lookup of inputVector at the same position. While it was already data-race free (the standard guarantees that concurrent loads do not induce data races), the less variables to read and write, the less there is to think about.

-
Also (yeah, still the same loop), I don't understand why you left the initialization of prime out of the thread: there is no point in leaving it out, and it forces the lambda to capture yet another parameter by reference, which would have been avoided had you declared prime` directly into the new thread.

StackExchange Code Review Q#66554, answer score: 5