Finding Prime Factors

Hello Everyone ,
   
In this post we will know how to find prime factors of a given number in a efficient way .
I assume that you know about the algorithm "Sieve of Eratosthenes" , if not then click here .
In this method we have the list of prime numbers generated from the above named algorithm.
Suppose we have a number N . A better way to find prime factors of this number is to express this number N as : N = PF x N'  , where PF is a prime factor and N' = N/PF . We keep doing so until N!=1
To speed up the process  even further, we utilize the divisibility property that there is no divisor greater than √N so we only repeat the process of finding prime factors until P F ≤ √N Stopping at √N entails a special case: If (current PF)^2  >N and N is still not 1 , then N is the last prime factor The code below takes in an  integer N and returns the list of prime factors.

#include <bitset>
#include<iostream>
#include<stdio.h>
#include<vector>
#define ll long long
using namespace std;
long long int _sieve_size;
bitset<10000010> bs;
vector<long long int> primes;

void sieve(long long int upperbound)
{
  // create list of primes in [0..upperbound]
 _sieve_size = upperbound + 1; // add 1 to include upperbound
 bs.set(); // set all bits to 1
 bs[0] = bs[1] = 0;// except index 0 and 1
 for (long long int  i = 2; i <= _sieve_size; i++)
 {
  if (bs[i])
  {
   // cross out multiples of i starting from i * i!
   for (long long int j = i * i; j <= _sieve_size; j += i)
   {
    bs[j] = 0;
   }
   primes.push_back((long long int)i);
   // add this prime to the list of primes
  }
 }
}


vector<ll int> primeFactors(ll N)
{
    vector<ll int>factors;
    ll PF_idx = 0 ,PF = primes[PF_idx];
    while(PF*PF<=N)   //stop at sqrt N
    {
        while(N%PF==0)
        {
            N = N/PF;
            factors.push_back(PF); // storing the prime factors in the vetors
        }
        PF = primes[++PF_idx];
    }
    if(N!=1){factors.push_back(N); }// in case when N is a prime
    return factors;
}
int main()
{


 sieve(10000000);
 vector<ll int>r = primeFactors(2147483647);
 for(vector<ll int>::iterator i = r.begin();i!= r.end();i++)
 {
    printf("> %lld\n", *i); // worst case as  2147483647 is a prime
 }

r = primeFactors(136117223861LL); // slower
 for(vector<ll int>::iterator i = r.begin();i!= r.end();i++)
 {
   printf("# %lld\n", *i);
 }

 r = primeFactors(36);  // faster,
  for(vector<ll int>::iterator i = r.begin();i!= r.end();i++)
 {
   printf("! %lld\n", *i);
 }

}