We can calculate the prime factorization of a number ānā in O(sqrt(n)) as discussed here. But O(sqrt n) method times out when we need to answer multiple queries regarding prime factorization.
In this article, we study an efficient method to calculate the prime factorization using O(n) space and O(log n) time complexity with pre-computation allowed.
Prerequisites : Sieve of Eratosthenes, Least prime factor of numbers till n.
Approach:Ā
The main idea is to precompute the Smallest Prime Factor (SPF) for each number from 1 to MAXN using the sieve function. SPF is the smallest prime number that divides a given number without leaving a remainder. Then, the getFactorization function uses the precomputed SPF array to find the prime factorization of the given number by repeatedly dividing the number by its SPF until it becomes 1.
To calculate to smallest prime factor for every number we will use the sieve of eratosthenes. In the original Sieve, every time we mark a number as not prime, we store the corresponding smallest prime factor for that number (Refer this article for better understanding).
Now, after we are done with precalculating the smallest prime factor for every number we will divide our number n (whose prime factorization is to be calculated) by its corresponding smallest prime factor till n becomes 1.Ā
Pseudo Code for prime factorization assuming
SPFs are computed :
PrimeFactors[] // To store result
i = 0 // Index in PrimeFactors
while n != 1 :
// SPF : smallest prime factor
PrimeFactors[i] = SPF[n]
i++
n = n / SPF[n]
Step-by-step approach of above idea:
- Defines a constant MAXN equal to 100001.
- An integer array spf of size MAXN is declared. This array will store the smallest prime factor for each number up to MAXN.
- A function sieve() is defined to calculate the smallest prime factor of every number up to MAXN using the Sieve of Eratosthenes algorithm.
- The smallest prime factor for the number 1 is set to 1.
- The smallest prime factor for every number from 2 to MAXN is initialized to be the number itself.
- The smallest prime factor for every even number from 4 to MAXN is set to 2.
- The smallest prime factor for every odd number from 3 to the square root of MAXN is calculated by iterating over all odd numbers and checking if the number is prime.
- If a number i is prime, then the smallest prime factor for all numbers divisible by i is set to i.
- A function getFactorization(int x) is defined to return the prime factorization of a given integer x using the spf array.
- The getFactorization(int x) function finds the smallest prime factor of x, pushes it to a vector, and updates x to be the quotient of x divided by its smallest prime factor. This process continues until x becomes 1, at which point the vector of prime factors is returned.
- In the main() function, the sieve() function is called to precalculate the smallest prime factor of every number up to MAXN. Then, the prime factorization of a sample integer x is found using the getFactorization(int x) function, and the result is printed to the console.
The implementation for the above method is given below :Ā
C++
// C++ program to find prime factorization of a// number n in O(Log n) time with precomputation// allowed.#include "bits/stdc++.h"using namespace std;Ā
#define MAXN 100001Ā
// stores smallest prime factor for every numberint spf[MAXN];Ā
// Calculating SPF (Smallest Prime Factor) for every// number till MAXN.// Time Complexity : O(nloglogn)void sieve(){Ā Ā Ā Ā spf[1] = 1;Ā Ā Ā Ā for (int i = 2; i < MAXN; i++)Ā
Ā Ā Ā Ā Ā Ā Ā Ā // marking smallest prime factor for everyĀ Ā Ā Ā Ā Ā Ā Ā // number to be itself.Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = i;Ā
Ā Ā Ā Ā // separately marking spf for every evenĀ Ā Ā Ā // number as 2Ā Ā Ā Ā for (int i = 4; i < MAXN; i += 2)Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = 2;Ā
Ā Ā Ā Ā for (int i = 3; i * i < MAXN; i++) {Ā Ā Ā Ā Ā Ā Ā Ā // checking if i is primeĀ Ā Ā Ā Ā Ā Ā Ā if (spf[i] == i) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking SPF for all numbers divisible by iĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j = i * i; j < MAXN; j += i)Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking spf[j] if it is notĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // previously markedĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (spf[j] == j)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[j] = i;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }}Ā
// A O(log n) function returning primefactorization// by dividing by smallest prime factor at every stepvector<int> getFactorization(int x){Ā Ā Ā Ā vector<int> ret;Ā Ā Ā Ā while (x != 1) {Ā Ā Ā Ā Ā Ā Ā Ā ret.push_back(spf[x]);Ā Ā Ā Ā Ā Ā Ā Ā x = x / spf[x];Ā Ā Ā Ā }Ā Ā Ā Ā return ret;}Ā
// driver program for above functionint main(int argc, char const* argv[]){Ā Ā Ā Ā // precalculating Smallest Prime FactorĀ Ā Ā Ā sieve();Ā Ā Ā Ā int x = 12246;Ā Ā Ā Ā cout << "prime factorization for " << x << " : ";Ā
Ā Ā Ā Ā // calling getFactorization functionĀ Ā Ā Ā vector<int> p = getFactorization(x);Ā
Ā Ā Ā Ā for (int i = 0; i < p.size(); i++)Ā Ā Ā Ā Ā Ā Ā Ā cout << p[i] << " ";Ā Ā Ā Ā cout << endl;Ā Ā Ā Ā return 0;} |
Java
// Java program to find prime factorization of a// number n in O(Log n) time with precomputation// allowed.Ā
import java.util.Vector;Ā
class Test{Ā Ā Ā Ā static final int MAXN = 100001;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // stores smallest prime factor for every numberĀ Ā Ā Ā static int spf[] = new int[MAXN];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Calculating SPF (Smallest Prime Factor) for everyĀ Ā Ā Ā // number till MAXN.Ā Ā Ā Ā // Time Complexity : O(nloglogn)Ā Ā Ā Ā static void sieve()Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā spf[1] = 1;Ā Ā Ā Ā Ā Ā Ā Ā for (int i=2; i<MAXN; i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking smallest prime factor for everyĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // number to be itself.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // separately marking spf for every evenĀ Ā Ā Ā Ā Ā Ā Ā // number as 2Ā Ā Ā Ā Ā Ā Ā Ā for (int i=4; i<MAXN; i+=2)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i=3; i*i<MAXN; i++)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // checking if i is primeĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (spf[i] == i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking SPF for all numbers divisible by iĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j=i*i; j<MAXN; j+=i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking spf[j] if it is not Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // previously markedĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (spf[j]==j)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[j] = i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // A O(log n) function returning primefactorizationĀ Ā Ā Ā // by dividing by smallest prime factor at every stepĀ Ā Ā Ā static Vector<Integer> getFactorization(int x)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Vector<Integer> ret = new Vector<>();Ā Ā Ā Ā Ā Ā Ā Ā while (x != 1)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ret.add(spf[x]);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā x = x / spf[x];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā return ret;Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Driver methodĀ Ā Ā Ā public static void main(String args[])Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // precalculating Smallest Prime FactorĀ Ā Ā Ā Ā Ā Ā Ā sieve();Ā Ā Ā Ā Ā Ā Ā Ā int x = 12246;Ā Ā Ā Ā Ā Ā Ā Ā System.out.print("prime factorization for " + x + " : ");Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // calling getFactorization functionĀ Ā Ā Ā Ā Ā Ā Ā Vector <Integer> p = getFactorization(x);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i=0; i<p.size(); i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.print(p.get(i) + " ");Ā Ā Ā Ā Ā Ā Ā Ā System.out.println();Ā Ā Ā Ā }} |
Python3
# Python3 program to find prime factorization # of a number n in O(Log n) time with # precomputation allowed.import math as mtĀ
MAXN = 100001Ā
# stores smallest prime factor for# every numberspf = [0 for i in range(MAXN)]Ā
# Calculating SPF (Smallest Prime Factor) # for every number till MAXN.# Time Complexity : O(nloglogn)def sieve():Ā Ā Ā Ā spf[1] = 1Ā Ā Ā Ā for i in range(2, MAXN):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # marking smallest prime factor Ā Ā Ā Ā Ā Ā Ā Ā # for every number to be itself.Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = iĀ
Ā Ā Ā Ā # separately marking spf for Ā Ā Ā Ā # every even number as 2Ā Ā Ā Ā for i in range(4, MAXN, 2):Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = 2Ā
Ā Ā Ā Ā for i in range(3, mt.ceil(mt.sqrt(MAXN))):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # checking if i is primeĀ Ā Ā Ā Ā Ā Ā Ā if (spf[i] == i):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # marking SPF for all numbersĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # divisible by iĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for j in range(i * i, MAXN, i): Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # marking spf[j] if it is Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # not previously markedĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (spf[j] == j):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[j] = iĀ
# A O(log n) function returning prime # factorization by dividing by smallest # prime factor at every stepdef getFactorization(x):Ā Ā Ā Ā ret = list()Ā Ā Ā Ā while (x != 1):Ā Ā Ā Ā Ā Ā Ā Ā ret.append(spf[x])Ā Ā Ā Ā Ā Ā Ā Ā x = x // spf[x]Ā
Ā Ā Ā Ā return retĀ
# Driver codeĀ
# precalculating Smallest Prime Factorsieve()x = 12246print("prime factorization for", x, ": ",Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā end = "")Ā
# calling getFactorization functionp = getFactorization(x)Ā
for i in range(len(p)):Ā Ā Ā Ā print(p[i], end = " ")Ā
# This code is contributed # by Mohit kumar 29 |
C#
// C# program to find prime factorization of a// number n in O(Log n) time with precomputation// allowed.using System;using System.Collections;Ā
class GFG{Ā Ā Ā Ā static int MAXN = 100001;Ā Ā Ā Ā Ā Ā Ā Ā Ā // stores smallest prime factor for every numberĀ Ā Ā Ā static int[] spf = new int[MAXN];Ā Ā Ā Ā Ā Ā Ā Ā Ā // Calculating SPF (Smallest Prime Factor) for everyĀ Ā Ā Ā // number till MAXN.Ā Ā Ā Ā // Time Complexity : O(nloglogn)Ā Ā Ā Ā static void sieve()Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā spf[1] = 1;Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 2; i < MAXN; i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking smallest prime factor for everyĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // number to be itself.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // separately marking spf for every evenĀ Ā Ā Ā Ā Ā Ā Ā // number as 2Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 4; i < MAXN; i += 2)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 3; i * i < MAXN; i++)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // checking if i is primeĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (spf[i] == i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking SPF for all numbers divisible by iĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int j = i * i; j < MAXN; j += i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking spf[j] if it is not Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // previously markedĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (spf[j] == j)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[j] = i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā // A O(log n) function returning primefactorizationĀ Ā Ā Ā // by dividing by smallest prime factor at every stepĀ Ā Ā Ā static ArrayList getFactorization(int x)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā ArrayList ret = new ArrayList();Ā Ā Ā Ā Ā Ā Ā Ā while (x != 1)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ret.Add(spf[x]);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā x = x / spf[x];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā return ret;Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā // Driver codeĀ Ā Ā Ā public static void Main()Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // precalculating Smallest Prime FactorĀ Ā Ā Ā Ā Ā Ā Ā sieve();Ā Ā Ā Ā Ā Ā Ā Ā int x = 12246;Ā Ā Ā Ā Ā Ā Ā Ā Console.Write("prime factorization for " + x + " : ");Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // calling getFactorization functionĀ Ā Ā Ā Ā Ā Ā Ā ArrayList p = getFactorization(x);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < p.Count; i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Console.Write(p[i] + " ");Ā Ā Ā Ā Ā Ā Ā Ā Console.WriteLine("");Ā Ā Ā Ā }}Ā
// This code is contributed by mits |
PHP
<?php// PHP program to find prime factorization // of a number n in O(Log n) time with // precomputation allowed.Ā
$MAXN = 19999;Ā
// stores smallest prime factor for // every number$spf = array_fill(0, $MAXN, 0);Ā
// Calculating SPF (Smallest Prime Factor) // for every number till MAXN.// Time Complexity : O(nloglogn)function sieve(){Ā Ā Ā Ā global $MAXN, $spf;Ā Ā Ā Ā $spf[1] = 1;Ā Ā Ā Ā for ($i = 2; $i < $MAXN; $i++)Ā
Ā Ā Ā Ā Ā Ā Ā Ā // marking smallest prime factor Ā Ā Ā Ā Ā Ā Ā Ā // for every number to be itself.Ā Ā Ā Ā Ā Ā Ā Ā $spf[$i] = $i;Ā
Ā Ā Ā Ā // separately marking spf for every Ā Ā Ā Ā // even number as 2Ā Ā Ā Ā for ($i = 4; $i < $MAXN; $i += 2)Ā Ā Ā Ā Ā Ā Ā Ā $spf[$i] = 2;Ā
Ā Ā Ā Ā for ($i = 3; $i * $i < $MAXN; $i++)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // checking if i is primeĀ Ā Ā Ā Ā Ā Ā Ā if ($spf[$i] == $i)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking SPF for all numbersĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // divisible by iĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for ($j = $i * $i; $j < $MAXN; $j += $i)Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking spf[j] if it is not Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // previously markedĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if ($spf[$j] == $j)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā $spf[$j] = $i;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }}Ā
// A O(log n) function returning primefactorization// by dividing by smallest prime factor at every stepfunction getFactorization($x){Ā Ā Ā Ā global $spf;Ā Ā Ā Ā $ret = array();Ā Ā Ā Ā while ($x != 1)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā array_push($ret, $spf[$x]);Ā Ā Ā Ā Ā Ā Ā Ā if($spf[$x])Ā Ā Ā Ā Ā Ā Ā Ā $x = (int)($x / $spf[$x]);Ā Ā Ā Ā }Ā Ā Ā Ā return $ret;}Ā
// Driver CodeĀ
// precalculating Smallest // Prime Factorsieve();$x = 12246;echo "prime factorization for " .Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā $x . " : ";Ā
// calling getFactorization function$p = getFactorization($x);Ā
for ($i = 0; $i < count($p); $i++)Ā Ā Ā Ā echo $p[$i] . " ";Ā
// This code is contributed by mits?> |
Javascript
<script>// Javascript program to find prime factorization of a// number n in O(Log n) time with precomputation// allowed.Ā Ā Ā Ā Ā Ā Ā Ā Ā let MAXN = 100001;Ā Ā Ā Ā Ā // stores smallest prime factor for every numberĀ Ā Ā Ā let spf=new Array(MAXN);Ā Ā Ā Ā Ā Ā Ā Ā Ā // Calculating SPF (Smallest Prime Factor) for everyĀ Ā Ā Ā // number till MAXN.Ā Ā Ā Ā // Time Complexity : O(nloglogn)Ā Ā Ā Ā function sieve()Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā spf[1] = 1;Ā Ā Ā Ā Ā Ā Ā Ā for (let i=2; i<MAXN; i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking smallest prime factor for everyĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // number to be itself.Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // separately marking spf for every evenĀ Ā Ā Ā Ā Ā Ā Ā // number as 2Ā Ā Ā Ā Ā Ā Ā Ā for (let i=4; i<MAXN; i+=2)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[i] = 2;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (let i=3; i*i<MAXN; i++)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // checking if i is primeĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (spf[i] == i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking SPF for all numbers divisible by iĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (let j=i*i; j<MAXN; j+=i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // marking spf[j] if it is not Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // previously markedĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (spf[j]==j)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā spf[j] = i;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā // A O(log n) function returning primefactorizationĀ Ā Ā Ā // by dividing by smallest prime factor at every stepĀ Ā Ā Ā function getFactorization(x)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā let ret =[];Ā Ā Ā Ā Ā Ā Ā Ā while (x != 1)Ā Ā Ā Ā Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā ret.push(spf[x]);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā x = Math.floor(x / spf[x]);Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā return ret;Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā // Driver methodĀ Ā Ā Ā Ā Ā Ā Ā Ā // precalculating Smallest Prime FactorĀ Ā Ā Ā sieve();Ā Ā Ā Ā let x = 12246;Ā Ā Ā Ā document.write("prime factorization for " + x + " : ");Ā Ā Ā Ā // calling getFactorization functionĀ Ā Ā Ā letĀ p = getFactorization(x);Ā Ā Ā Ā for (let i=0; i<p.length; i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā document.write(p[i] + " ");Ā Ā Ā Ā Ā Ā Ā Ā document.write("<br>");Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā
// This code is contributed by unknown2108</script> |
Output:Ā
prime factorization for 12246 : 2 3 13 157
Time Complexity: O(log n), for each query (Time complexity for precomputation is not included)
Auxiliary Space: O(1)
Note : The above code works well for n upto the order of 10^7. Beyond this we will face memory issues.
Time Complexity: The precomputation for smallest prime factor is done in O(n log log n) using sieve. Whereas in the calculation step we are dividing the number every time by the smallest prime number till it becomes 1. So, letās consider a worst case in which every time the SPF is 2 . Therefore will have log n division steps. Hence, We can say that our Time Complexity will be O(log n) in worst case.
This article is contributed by Nitish Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ā
Feeling lost in the world of random DSA topics, wasting time without progress? Itās time for a change! Join our DSA course, where weāll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
