Prime Factorization

Prime Factorization is the process of breaking a number down into its basic building blocks (primes).

According to the Fundamental Theorem of Arithmetic, every integer \(>1\) has a unique set of prime factors.

  • \(12 = 2 \times 2 \times 3\) (or \(2^2 \times 3\))
  • \(100 = 2 \times 2 \times 5 \times 5\)
  • \(13 = 13\) (Prime)

Method 1: Trial Division (Good for large \(N\))

If you have a big number (like \(10^{12}\)), we use the logic from our “Divisors” lesson. We iterate from \(2\) up to \(\sqrt{N}\).

The Algorithm: 1. Start with \(d=2\). 2. While \(d\) divides \(N\), keep dividing \(N\) by \(d\) and record \(d\). 3. Increment \(d\). 4. Crucial Step: If after the loop \(N > 1\), the remaining \(N\) is a prime itself.

#include <iostream>
#include <vector>
using namespace std;

void factorize(long long n) {
    cout << "Factors of " << n << ": ";
    
    for (long long i = 2; i * i <= n; i++) {
        // While i divides n, it is a factor
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
        }
    }
    
    // EDGE CASE: If n is still > 1, it is a prime factor
    if (n > 1) {
        cout << n;
    }
    cout << endl;
}

Why does this work?

By the time we reach \(5\), we have already divided out all factors of \(2\), so \(N\) cannot be divisible by \(4\).

We strip the number down until only the last prime remains.

Complexity: \(O(\sqrt{N})\).

Method 2: SPF Optimization (Good for Many Queries)

If you need to factorize 100,000 numbers (where each number is small, \(< 10^7\)), Method 1 is too slow.

We can use a modified Sieve to factorize in Logarithmic time (\(O(\log N)\)).

###The Idea: SPF (Smallest Prime Factor)

Instead of storing true/false in our Sieve, we store the Smallest Prime Factor for every number. - spf[10] = 2 - spf[15] = 3 - spf[7] = 7 (it’s prime)

Once we have this array, we can “jump” down the number instantly. \(N \to N / spf[N] \to \dots \to 1\)

Precomputation

const int MAXN = 1000000;
int spf[MAXN + 1];

void sieve() {
    // Initialize: smallest prime factor of i is i itself
    for (int i = 1; i <= MAXN; i++) spf[i] = i;

    for (int i = 2; i * i <= MAXN; i++) {
        if (spf[i] == i) { // If i is prime
            for (int j = i * i; j <= MAXN; j += i) {
                // Mark smallest factor for j if not marked yet
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

Fast Factorization Query

vector<int> getFactors(int x) {
    vector<int> ret;
    while (x != 1) {
        ret.push_back(spf[x]);
        x = x / spf[x]; // Divide by smallest prime and continue
    }
    return ret;
}

Complexity: \(O(\log N)\) per query.

Which one to use?

Scenario Method Complexity
\(N\) is huge (\(10^{12}\)) Trial Division \(O(\sqrt{N})\)
Many Queries, \(N\) is small (\(10^7\)) SPF (Sieve) \(O(\log N)\)
Memory is tight Trial Division \(O(1)\)

The Perfect Square Inventory

The Perfect Square Inventory

A warehouse manager has received a shipment of \(n\) identical square storage boxes. He wants to stack them on the floor to form a perfect square arrangement (e.g., \(10 \times 10\), \(20 \times 20\)). However, he realizes that \(n\) may be not a perfect square number, so he cannot form a square with the current stock.

He decides to order more shipments of the exact same size (\(n\) boxes each per each shipment) until the total number of boxes allows him to build a perfect square.

What is the minimum number of shipments (including the first one) he needs to have in total?

Solution

This is a factorization problem because we are asking: “By what integer \(k\) must we multiply \(n\) so that the result is a perfect square?”

When we factorize the number into primes, in order to make it a perfect square, each exponent should be even. For example \(15 = 3^1 \cdot 5^1\), we should multiple by \(3\cdot 5\) to make the number \(225 = 3^2\cdot5^2\). On the other hand, number \(64 = 2^6\) is already a perfect square.

So in essence, for each odd exponent we should multiple the number with that prime.

#include <iostream>
using namespace std;

// Function to find the smallest multiplier to make 'n' a perfect square
int findSmallestMultiplier(int n) {
    int multiplier = 1;

    // Step 1: Check for divisibility by 2
    int count = 0;
    while (n % 2 == 0) {
        count++;
        n /= 2;
    }
    // If the count of 2s is odd, we need one more 2 to make a pair
    if (count % 2 != 0) {
        multiplier *= 2;
    }

    // Step 2: Check for odd factors (3, 5, 7, ...)
    for (int i = 3; i * i <= n; i += 2) {
        count = 0;
        while (n % i == 0) {
            count++;
            n /= i;
        }
        // If the count of this factor is odd, we need one more to make a pair
        if (count % 2 != 0) {
            multiplier *= i;
        }
    }

    // Step 3: Handle the remaining prime number (if any)
    // If n > 2 at this point, the remaining n is a prime factor with a count of 1 (odd)
    if (n > 2) {
        multiplier *= n;
    }

    return multiplier;
}

int main() {
    int n;
    cin >> n;

    int necessary_shipments = findSmallestMultiplier(n);
    cout << necessary_shipments << "\n";

    return 0;
}

For example, let \(n = 540\). The code will return 15. Let’s check whether this is correct. \(540\cdot 15 =8100 = 90^2\). We can also make sure this is the smallest such number by trying the smaller ones and seeing that they don’t work.