I. In-Class Exercises

Programming Exercises

1. Find the Larger Prime Factor: L3061
2. GESP Level 5 2309 Prime Factorization: L3062
3. GESP Level 5 2406 Xiaoyang's Lucky Number: L3063

II. Knowledge Summary

Core Idea

The Fundamental Theorem of Arithmetic states that every natural number greater than 1 can be written as a product of prime numbers, and this factorization is unique except for the order of the factors.

This theorem is the foundation of prime factorization.

Unique Factorization Form

Any integer n > 1 can be written as:

n = p1^k1 * p2^k2 * ... * pm^km

where p1, p2, ..., pm are distinct primes and k1, k2, ..., km are positive integers.

For example:

60 = 2^2 * 3^1 * 5^1

Basic Implementation

The standard method tries all possible factors from 2 up to sqrt(n). For each factor, divide repeatedly and count its exponent.

1#include <iostream>
2#include <vector>
3#include <cmath>
4using namespace std;
5
6struct Factor {
7    int base;
8    int exponent;
9};
10
11void factorize(int n) {
12    vector<Factor> factors;
13
14    int count = 0;
15    for (int i = 2; i <= sqrt(n); i++) {
16        count = 0;
17        while (n % i == 0) {
18            count++;
19            n /= i;
20        }
21        if (count > 0) {
22            factors.push_back(Factor{i, count});
23        }
24    }
25
26    if (n > 2) {
27        factors.push_back(Factor{n, 1});
28    }
29
30    for (int i = 0; i < factors.size(); i++) {
31        cout << factors[i].base << "^" << factors[i].exponent << " ";
32    }
33}
34
35int main() {
36    int number;
37    cout << "Enter a positive integer: ";
38    cin >> number;
39
40    cout << "Prime factorization of " << number << " is: ";
41    factorize(number);
42
43    return 0;
44}

Execution Example

Factorize 360:

Final result: 360 = 2^3 × 3^2 × 5^1

Optimized Implementation

We can optimize by removing all factors of 2 first. After that, n becomes odd, so we only need to test odd factors 3, 5, 7, ....

1#include <iostream>
2#include <vector>
3#include <cmath>
4using namespace std;
5
6struct Factor {
7    int base;
8    int exponent;
9};
10
11void factorize(int n) {
12    vector<Factor> factors;
13
14    int count = 0;
15    while (n % 2 == 0) {
16        count++;
17        n /= 2;
18    }
19    if (count > 0) {
20        factors.push_back(Factor{2, count});
21    }
22
23    for (int i = 3; i <= sqrt(n); i += 2) {
24        count = 0;
25        while (n % i == 0) {
26            count++;
27            n /= i;
28        }
29        if (count > 0) {
30            factors.push_back(Factor{i, count});
31        }
32    }
33
34    if (n > 2) {
35        factors.push_back(Factor{n, 1});
36    }
37
38    for (int i = 0; i < factors.size(); i++) {
39        cout << factors[i].base << "^" << factors[i].exponent << " ";
40    }
41}
42
43int main() {
44    int number;
45    cout << "Enter a positive integer: ";
46    cin >> number;
47
48    cout << "Prime factorization of " << number << " is: ";
49    factorize(number);
50
51    return 0;
52}

Execution Example

Again for 360:

• First remove all 2s: 360 -> 180 -> 90 -> 45, so record 2^3
• Then test odd factors:
  • 3: 45 -> 15 -> 5, so record 3^2
• End of loop, remaining n = 5, so record 5^1

This version checks fewer candidates and is faster.

Why Unique Factorization Matters

It matters because it supports:

• GCD and LCM computation
• prime testing
• many results in number theory
• cryptography, such as RSA

Problem-Solving Steps

For factorization problems:

1. Choose a method:
   • Basic method is usually enough
   • For large n, use the optimized odd-factor version
2. Start from the smallest prime factor
3. Only loop up to sqrt(n)
4. If n > 1 after the loop, record the remaining n
5. Store both the factor and its exponent

Common Mistakes

• Using i < n instead of i <= sqrt(n)
• Forgetting to handle the remaining n > 1
• Not resetting count
• Running into floating-point sqrt precision issues
• Forgetting that 1 has no prime factorization

III. Homework

Programming Exercises

1. Prime Factorization: L3064