Problem Statement

Calculate the prime factorization of an unsigned integer [0,2^32-1]. Represent the factorization in the natural format.

Solution

It uses seive to calculate all the primes upto n = 2^16 (p = 6542 primes in this range) then uses those primes to factorize the all the numbers upto N = 2^32.

Prime factorization of a non prime number k will contain at least one factor less than sqrt(k), otherwise k is prime. Hence we only need to precalculate all the primes upto 2^16 only, and we can find all other factors recursively.

• Once we got the all the primes, we can just iterate over all the primes.
• Once we find a factor of the number we can reduce the search space substantially.
• If we divide the number by factor then the factors for the remaining number will also be factors of original number.
• Hence we can repeat the same procedure for remaining number until the number is 1 or we run out of our calculated primes to compare for.
• In the later case the remaining number is a prime as well, which would be greater than n=sqrt(N)

Complexity

• Precomputation
  • Time: O(n*log(n)) = O(sqrt(N)*log(N))
    because sum_upto_sqrt_n(n/i-i) ~ (n*log(n) - n)/2
  • Space: O(p) ~ O(n/log(n))
    because of prime number theorem
• Factorization
  • Time: O(p*log(N)) ~ O(n) = O(sqrt(N)) Upper bound. Maximum number of factors of a number = log(N). Length of the array = p.
  • Extra Space: O(1) Only constant space is used, other than the space to store factorization itself.
• Legend
  • N: maximum input number
  • n: sqrt(N)
  • p: number of primes found less than n ~ n/log(n)
• Bonus
  • Factorization Time complexity tight bound: O(p) ~ O(n/log(n)) = O(sqrt(N)/log(N))
  • Some more tight bound on factorization part, reveals that on an average square or cube of the calculated primes, goes off the ceiling. Only a few dozen of initial numbers is more than 5th or 6th power. Hence the total comparisons can be as less as 2*p
  • Hence making the overall time complexity for factorization linear in p
  • analysis can be found here https://ideone.com/kJzElq

    Bonus

    Natural way of writing a number in it’s constituent parts. This reveals everything about that number.

Link

https://ideone.com/DuqFYy

Usage

https://leetcode.com/submissions/detail/388808430/ https://leetcode.com/submissions/detail/708379160/

Code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;
int N=65537;
vector<bool> a(N,false);
vector<int> prime;

string getPrint(const map<int,int> &v){
	string s;
	stringstream ss;
	for(auto p: v)
		if(p.second==1)	ss<<p.first<<'*';
		else	ss<<'('<<p.first<<'^'<<p.second<<')'<<'*';
	ss>>s;
	s.pop_back();
	return s;
}

map<int,int> primeFactorization(unsigned int n){
	map<int,int> v;
	int i=0;
	int c=0;
	int l=prime.size();
	int p;
	int s = sqrt(n);
	while(n>1){
		while(i<l&&prime[i]<=s&&n%prime[i])	i++;
		if(i==l||prime[i]>s)	p = n;
		else	p = prime[i];
		c=0;
		while(n%p==0){
			n /= p;
			c++;
		}
		v[p] = c;
		s = sqrt(n);
	}
	return v;
}

void initializePrimes(){
	int m, n=N;
	a[0]=a[1]=true;
	for(int i=0; i<=sqrt(n); i++){
		if(a[i])	continue;
		prime.push_back(i);
		m = i*i;
		while(m<n){
			a[m]=true;
			m += i;
		}
	}
	for(int i=sqrt(n); i<n; i++)
		if(!a[i])	prime.push_back(i);
	
	cout<<"Prime size is "<<prime.size()<<endl;
}

int main() {
	initializePrimes();
	int t,n;
	cin>>t;
	while(t--){
		cin>>n;
		cout<<n<<" = "<<getPrint(primeFactorization(n))<<endl;
	}
	return 0;
}

Ideone it!

Usage

• Usage 1

• Usage 2