Factorization with prime Sieve

1. vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); for ( int i = 4; i <= N; i += 2 ) sieve[i] = 1; int sqrtn = sqrt ( N ); for ( int i = 3; i <= sqrtn; i += 2 ) { if ( sieve[i] == 0 ) { for ( int j = i * i; j <= N; j += 2 * i ) sieve[j] = 1; } } for ( int i = 3; i <= N; i += 2 ) if ( sieve[i] == 0 ) prime.push_back(i); }
2. vector <int> factors; void factorize( ll n ) { ll sqrtn = sqrt ( n ); for ( ll i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) { if ( n % prime[i] == 0 ) { while ( n % prime[i] == 0 ) { n /= prime[i]; factors.push_back(prime[i]); } sqrtn = sqrt ( n ); } } if ( n != 1 ) { factors.push_back(n); } }