title: Efficient Prime Factorization for large numbers
body: <p>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. </p>
  
  <p>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.</p>
  
  <p>I noticed a few algorithms like <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noreferrer">Sieve of Eratosthenes</a> 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!</p>
  
  <p>Here is my code: </p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;thread&gt;
  #include &lt;vector&gt;
  #include &lt;chrono&gt;
  
  using namespace std;
  using namespace std::chrono;
  
  vector&lt;thread&gt; threads;
  vector&lt;long long&gt; inputVector;
  bool developer = false; 
  vector&lt;unsigned long long&gt; factor_base;
  vector&lt;long long&gt; primeVector;
  
  class PrimeNumber
  {
      long long initValue;        // the number being prime factored
      vector&lt;long long&gt; 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&lt;long long&gt; m)
      {
          factors = m;
      }
      long long getInitValue()
      {
          return initValue;
      }
      vector&lt;long long&gt; getVector()
      {
          return factors;
      }
  };
  
  vector&lt;PrimeNumber&gt; primes;
  
  // find primes recursively and have them returned in vectors
  vector&lt;long long&gt; getPrimes(long long n, vector&lt;long long&gt; vec)
  {
      double sqrt_of_n = sqrt(n);
  
      for (int i = 2; i &lt;= sqrt_of_n; i++)
      {
          if (n % i == 0) 
          {
              return vec.push_back(i), getPrimes(n / i, vec); //cause recursion
          }
      }
  
      // pick up the last prime factorization number
      vec.push_back(n);
  
      //return the finished vector
      return vec;
  }
  
  void getUserInput()
  {
      long long input = -1;
      cout &lt;&lt; "Enter all of the numbers to find their prime factors. Enter 0 to compute" &lt;&lt; endl;
      do
      {
          cin &gt;&gt; input;
          if (input == 0)
          {
              break;
          }
          inputVector.push_back(input);
      } while (input != 0);
  }
  
  int main() 
  {
  
      vector&lt;long long&gt; temp1;   // empty vector
      vector&lt;long long&gt; result1; // temp vector
  
      if (developer == false)
      {
          getUserInput();
      }
      else
      {
          cout &lt;&lt; "developer mode active" &lt;&lt; endl;
          long long a1 = 771895004973090566;
          long long b1 = 788380500764597944;
          long long a2 = 100020000004324000;
          long long b2 = 200023423420000000;
          inputVector.push_back(a1);
          inputVector.push_back(b2);
          inputVector.push_back(b1);
          inputVector.push_back(a2);
      }
  
      high_resolution_clock::time_point time1 = high_resolution_clock::now();
  
      // give each thread a number to comput within the recursive function
      for (int i = 0; i &lt; inputVector.size(); i++)
      {   
          PrimeNumber prime;
          prime.setInitValue(inputVector.at(i));
          threads.push_back(thread([&amp;]{
              prime.setVector(result1 = getPrimes(inputVector.at(i), temp1));
              primes.push_back(prime);
          }));
      }
  
      // allow all of the threads to join back together.
      for (auto&amp; th : threads)
      {
          cout &lt;&lt; th.get_id() &lt;&lt; endl;
          th.join();
      }
  
      high_resolution_clock::time_point time2 = high_resolution_clock::now();
  
      // print all of the information
      for (int i = 0; i &lt; primes.size(); i++)
      {
          vector&lt;long long&gt; temp = primes.at(i).getVector();
  
          for (int m = 0; m &lt; temp.size(); m++)
          {
              cout &lt;&lt; temp.at(m) &lt;&lt; " ";
          }
          cout &lt;&lt; endl;
      }
  
      cout &lt;&lt; endl;
  
      // so the running time
      auto duration = duration_cast&lt;microseconds&gt;(time2 - time1).count();
  
      cout &lt;&lt; "Duration: " &lt;&lt; (duration / 1000000.0) &lt;&lt; endl;
  
      return 0;
  }
  </code></pre>