title: Fastest way to prime factorise a number up to 10^18
body: <p>Given a number <code>1 &lt;= n &lt;= 10^18</code>, how can I factorise it in least time complexity?</p>
  
  <p>There are many posts on the internet addressing how you can find prime factors but none of them (at least from what I've seen) state their benefits, say in a particular situation.</p>
  
  <p>I use Pollard's rho algorithm in addition to Eratosthenes' sieve:</p>
  
  <ul>
  <li>Using sieve, find all prime numbers in the first 10<sup>7</sup> numbers, and then divide <code>n</code> with these primes as much as possible.</li>
  <li>Now use Pollard's rho algorithm to try and find the rest of the primes until n is equal to 1. </li>
  </ul>
  
  <p>My Implementation:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;cstdio&gt;
  #include &lt;ctime&gt;
  #include &lt;cmath&gt;
  #include &lt;cstdlib&gt;
  #include &lt;algorithm&gt;
  #include &lt;string&gt;
  
  using namespace std;
  
  typedef unsigned long long ull;
  typedef long double ld;
  typedef pair &lt;ull, int&gt; pui;
  #define x first
  #define y second
  #define mp make_pair
  
  bool prime[10000005];
  vector &lt;ull&gt; p;
  
  void initprime(){
      prime[2] = 1;
      for(int i = 3 ; i &lt; 10000005 ; i += 2){
          prime[i] = 1;
      }
      for(int i = 3 ; i * i &lt; 10000005 ; i += 2){
          if(prime[i]){
              for(int j = i * i ; j &lt; 10000005 ; j += 2 * i){
                  prime[j] = 0;
              }
          }
      }
      for(int i = 0 ; i &lt; 10000005 ; ++i){
          if(prime[i]){
              p.push_back((ull)i);
          }
      }
  }
  
  ull modularpow(ull base, ull exp, ull mod){
      ull ret = 1;
      while(exp){
          if(exp &amp; 1){
              ret = (ret * base) % mod;
          }
          exp &gt;&gt;= 1;
          base = (base * base) % mod;
      }
      return ret;
  }
  
  ull gcd(ull x, ull y){
      while(y){
          ull temp = y;
          y = x % y;
          x = temp;
      }
      return x;
  }
  
  ull pollardrho(ull n){
      srand(time(NULL));
      if(n == 1)
          return n;
      ull x = (rand() % (n - 2)) + 2;
      ull y = x;
      ull c = (rand() % (n - 1)) + 1;
      ull d = 1;
      while(d == 1){
          x = (modularpow(x, 2, n) + c + n) % n;
          y = (modularpow(y, 2, n) + c + n) % n;
          y = (modularpow(y, 2, n) + c + n) % n;
          d = gcd(abs(x - y), n);
          if(d == n){
              return pollardrho(n);
          }
      }
      return d;
  }
  int main ()
  {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  initprime();
  ull n;
  cin &gt;&gt; n;
  ull c = n;
  vector &lt;pui&gt; o;
  for(vector &lt;ull&gt;::iterator i = p.begin() ; i != p.end() ; ++i){
      ull t = *i;
      if(!(n % t)){
          o.push_back(mp(t, 0));
      }
      while(!(n % t)){
          n /= t;
          o[o.size() - 1].y++;
      }
  }
  while(n &gt; 1){
      ull u = pollardrho(n);
      o.push_back(mp(u, 0));
      while(!(n % u)){
          n /= u;
          o[o.size() - 1].y++;
      }
      if(n &lt; 10000005){
          if(prime[n]){
              o.push_back(mp(n, 1));
          }
      }
  }
  return 0;
  }
  </code></pre>
  
  <p>Is there any faster way to factor such numbers? If possible, please explain why along with the source code.</p>