When run in GDB, it has no issues. When not, it runs indefinitely (well... I can't really say that for sure... I can say it runs for a long time).

Also, I realise this is a total hack of a way to do this. I'm open to, and glad for, any suggestions.

main.cpp
Code:
#include "prime.hpp"

#include <iostream>
#include <map>
#include <thread>
#include <utility>
#include <vector>

#define MAX_THREADS 16
using namespace std;

void wrapper(mpz_class n, map<mpz_class, set<mpz_class>> &factor_list, bool &state)
{
    auto factors = factor(n);
    
    factor_list.insert(pair<mpz_class, set<mpz_class>>(n, factors));
    
    state = false;
}

int main()
{
    map<mpz_class, set<mpz_class>> factors;
    vector<pair<thread, bool>> threads;
    
    for(mpz_class n = 2;n <= 10;n++)
    {
        while(threads.size() >= MAX_THREADS)
            for(auto i = threads.begin();i < threads.end();i++)
                if(i->second == false)
                {
                    if(i->first.joinable())
                        i->first.join();
                    
                    threads.erase(i);
                }
        
        threads.push_back(pair<thread, bool>(thread(), true));
        threads.back().first = thread(wrapper, n, std::ref(factors), std::ref(threads.back().second));
    }
    
    
    while(threads.size() > 0)
        for(auto i = threads.begin();i < threads.end();i++)
            if(i->second == false)
            {
                if(i->first.joinable())
                    i->first.join();
                
                threads.erase(i);
            }
        
    for(auto i = factors.begin();i != factors.end();i++)
    {
        std::cout << i->first.get_str() << ": ";
        
        for(auto j = i->second.begin();j != i->second.end();j++)
            std::cout << j->get_str() << " ";
        
        std::cout << std::endl;
    }
    
    return 0;
}
prime.hpp
Code:
#ifndef PRIME_HPP
#define PRIME_HPP

#include "gmpxx.h"

#include <set>

std::set<mpz_class> factor(mpz_class);
bool prime(mpz_class);

#endif // PRIME_HPP
prime.cpp (Included for completeness. I don't believe this code is the problem.)
Code:
#include "prime.hpp"

#include <thread>
#include <vector>

static std::vector<mpz_class> primes{2, 3};

static void extend_primes(mpz_class n)
{
    // Unfortunately, primes can't effeciently, if at all, be extended concurrently...
    static std::mutex m;
    std::lock_guard<std::mutex> lock(m);
    
    for(mpz_class i = primes.back() + 2;i <= n;i += 2)
    {
        bool prime = true; // Assume i is prime.
        
        for(auto j = primes.begin();prime && *j <= sqrt(i);j++)
            if(i % *j == 0)
                prime = false;
        
        if(prime)
            primes.push_back(i);
    }
}

std::set<mpz_class> factor(mpz_class n)
{
    std::set<mpz_class> factors;
    
    extend_primes(n);
    
    for(auto i = primes.begin();*i <= n / 2;i++)
        if(n % *i == 0)
            factors.insert(*i);
    
    return factors;
}

bool prime(mpz_class n)
{
    extend_primes(sqrt(n));
    
    for(auto i = primes.begin();*i <= sqrt(n);i++)
    {
        if(n % *i == 0)
            return false;
    }
    
    return true;
}
Compiled with:
Code:
gcc -g -pthread -std=c++0x -lstdc++ -lgmp -o prime main.cpp prime.cpp
Desired output:
Code:
2:
3:
4: 2
5:
6: 2 3
7:
8: 2
9: 3
10: 2 5