title: Is there a way to factorize large numbers in c++
body: <p>I've written the following C++ code to factorize really large numbers efficiently (numbers up to 24997300729).
  I have a vector containing 41000 primes approx.( I know having such a large vector isn't a good idea although but couldn't figure a way around this).
  This code produces the prime factorization of moderately large numbers in no time but when it comes to numbers such as, 24997300572 the program <em>stalls</em>.</p>
  
  <p>Here's the program below with some screenshots of the output:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  #include &lt;iterator&gt;
  #include &lt;cmath&gt;
  
  using namespace std;
  
  vector&lt;int&gt; primes = {paste from  
  
     https://drive.google.com/file/d/1nGvtMMQSa9YIDkMW2jgEbJk67P7p54ft/view?usp=sharing
  };
  
  void factorize(int n) {
      if (n == 1)
          return;
      if (find(primes.begin(), primes.end(), n) != primes.end()) {
          cout &lt;&lt; n &lt;&lt;" ";            //if n is prime dont'proceed further
          return;
      }
  
      //obtaining an iterator to the location of prime equal to or just greater than sqrt(n)
      auto s = sqrt(n);
      vector&lt;int&gt;::iterator it = lower_bound(primes.begin(), primes.end(), s);
  
      if (it == primes.end()) {
          return;                 // if no primes found then the factors are beyond range
      }
      for (auto i = it;i != primes.begin();i--) {
          if (n % *i == 0)
          {
              cout &lt;&lt; *i &lt;&lt; " ";
              n = n / (*i);
              factorize(n);
              return;             // the two consecutive for() loops should never run one after another
          }
  
      }
      for (auto i = it;i != primes.end();i++) {
          if (n % *i == 0)
          {
              cout &lt;&lt; *i &lt;&lt; " ";
              n = n / (*i);
              factorize(n);
              return;         // the two consecutive for() loops should never run one after another
          }
      }
  }
  
  int main() {
      unsigned int n;
      cout &lt;&lt; "Enter a number between 1 and 24997300729 ";
      cin &gt;&gt; n;
      if (n &gt; 24997300729) {
          cout &lt;&lt; "Number out of range;";
          exit(-1);
      }
      factorize(n);
      return 0;
  }
  </code></pre>
  
  <p>This is OK</p>
  
  <p><img src="https://i.stack.imgur.com/09v91.jpg" alt="This is Ok"></p>
  
  <p>But This is NOT!!!</p>
  
  <p><img src="https://i.stack.imgur.com/XhV2h.jpg" alt="But This is NOT"></p>
  
  <p>I tried using <code>long long int</code> and <code>long double</code> wherever I could to over come the problem of large numbers, but that didn't help much.</p>
  
  <p><strong>Any help Would Be Greatly Appreciated</strong></p>