C++ program to find the prime factorization in O(Log(N))














































C++ program to find the prime factorization in O(Log(N))



/* C++ program to find the prime factorization of number in Log(n) time. In this article, We shall learn how to find the prime factorization of a number (1 <= number <= 10^6) We can achieve a log(n) time complexity for prime factorization of a number by storing the shortest prime factor for all numbers up to 10^6. This can be done by making use of sieve of eratosthenese. for any number N, number of prime factors <= log2(N). */ #include <iostream> #include <vector> #include <cassert> #define SZ(z) ((int)z.size()) using namespace std; const int N = 1000001; bool p[N]; // p[i] is true if i is prime and false otherwise int spf[N]; // spf[i] is shortest prime factor of i void process() { memset(p, true, sizeof p); memset(spf, -1, sizeof spf); p[0] = p[1] = false; int i; for (i = 2; i * i < N; i++) { if (p[i]) { spf[i] = i; for (int j = i * i; j < N; j += i) { p[j] = false; if (spf[j] == -1) spf[j] = i; } } } for (; i < N; i++) { if (spf[i] == -1) spf[i] = i; } } vector<pair<int, int> > factorize(int num) { /* This function returns prime factorization of a number say X If X = (p1^a)*(p2^b)*(p3^c)* ... Then returned vector will be V = {{p1,a},{p2,b},{p3,c}, ....} */ assert(num > 0 && num < N); // assertion for validating input vector<pair<int, int> > f; f.clear(); while (num != 1){ if (SZ(f) > 0 && f[SZ(f) - 1].first == spf[num]) { f[SZ(f) - 1].second++; } else { f.push_back({spf[num],1}); } num /= spf[num]; } if (SZ(f) == 0) f.push_back({ 1,1 }); return f; } void showfactorization(vector<pair<int, int> > f, int num) { cout << num << " ="; for (int i = 0; i < SZ(f); i++) { if (i > 0) { cout << '*'; } cout << " (" << f[i].first << '^' << f[i].second << ") "; } cout << '\n'; } int main() { process(); // takes O(N*log(log(N)) time only once where N is upper limit of input int num = 504; showfactorization(factorize(num), num); num = 12345; showfactorization(factorize(num), num); num = 123456; showfactorization(factorize(num), num); return 0; }

Comments