In the previous article, we've seen how we can calculate the prime factorization of a single number. Today, we'll focus on how we can efficiently find factorization in a range $[1, n]$. If you understand the sieve algorithm to find prime numbers, you're good to go. In case you don't know the sieve algorithm, you can read this article, Sieve of Eratosthenes – Generate prime numbers.

In the sieve algorithm, we start with $2$ and we mark all proper multiples of $2$ of the form $2k$ where $k > 1$ as composite. We then go the next unmarked number and simulate the same process. The idea is that, when we get a prime number $p$, and mark all the multiples of that prime $kp$ as composite (where $k>1$), we can say that $p$ is a prime factor of that multiple $kp$. This way we can store all the prime factors of a number in vector. Since we are doing factorization in a range, we'll need multiple vectors. Let's take a look at the code below:

bool marks[10010];
// array of vectors to store the facorization
vector<int> fact[10010];

void sieve_factorization(int n) {
  for (int i = 2; i <= n; ++i) {
    if (marks[i])
      continue; // if i is composite

    // otherwise 'i' is prime
    // so we find all the multiples of i

    for (int j = 2 * i; j <= n; j += i) {
      marks[j] = 1; //  mark those as composite

      // we know i is a prime factor of j
      // so we push that into fact[j]
      fact[j].push_back(i);
    }

    // i is a prime
    // so it is a prime factor of itself
    fact[i].push_back(i);
  }
}

When we invoke the function with $n$ as parameter, $fact[x]$ ($x \leq n$) will contain all the prime factors of $x$. We've computed all the prime factors. But we still don't know how many times the prime factor exists. So, for each prime factor $p_i$, we need to calculate its power $i$. There are two simple approaches that we can follow

• When we need factorization, we calculate the power of each prime factors
• Calculate prime factorization for all the numbers using the first approach

To get the facotorization of a single value from it's prime factors, we can calculate the power for each prime factor $p_i$ of $x$ where $x$ is the desired number which we want to factorize. Note that, you must call the sieve_factorization function before doing this.

// make sure you call sieve_factorization function
sieve_factoriztaion(1000);
// which stores all the prime factors in the vectors

void get_factorization(int x) {
  // for each prime factor
  for (auto pf : fact[x]) {
    int k = x, p = 0;
    // while x(100) is divisible by the prime factor
    while (k % pf == 0) {
      p++;     // increase power
      k /= pf; // eliminate pf from x
    }
    // printing out the factorization
    cout << pf << '^' << p << endl;
  }
}

We can also precalculate the factorization. The idea is quite same. For each prime $p$, we visit every compsite of the form $kp$ where $k > 1$ and for each composite $c$, while it is divisible by $p$ we keep dividing it by $p$ and simply count the number of occurances.

bool marks[10010];
vector<pair<int, int>> fact[10010];

void sieve_factorization(int n) {
  for (int i = 2; i <= n; ++i) {
    if (marks[i])
      continue; // if i is composite

    // otherwise 'i' is prime
    // so we find all the multiples of i
    for (int j = 2 * i; j <= n; j += i) {
      marks[j] = 1; // mark those as composite

      // and we know i is a prime factor of j
      // we don't know how many times the prime occurs
      // so we calculate the number of occurances
      int c = j, k = 0;
      while (c % i == 0) {
        c /= i;
        k++;
      }
      // i is the prime
      // and it is raised to the power k
      fact[j].push_back({i, k});
    }
    // i is a prime
    // so it is a prime factor of itself
    // and it is raised to the power 1
    fact[i].push_back({i, 1});
  }
}