Number Theory I 📚

Agenda

1. Divisors
2. Primes
3. Prime Factorization
4. Sieve of Eratosthenes
5. Applications
   • Count divisors of N using its prime factorization
   • Count divisors for all numbers in range [1, N]
6. Practice Problems

1. Divisors ⚙️

• To find divisors of a number N, iterate through numbers 1 to sqrt(N).
• For each number, check if it divides N; if true, also record its complementary divisor N/i.

Time Complexity: O(sqrt(N))

vector<int> get_divisors(int n) {
    vector<int> divisors;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) divisors.push_back(n / i);
        }
    }
    return divisors;
}

int main() {
    int n;
    cin >> n;
    auto divisors = get_divisors(n);
    for (auto d: divisors) cout << d << " ";
}

2. Primes 🔑

• A prime number has exactly two divisors: 1 and the number itself.
• To check if a number is prime, test divisibility up to sqrt(N).

Time Complexity: O(sqrt(N))

bool isPrime(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return n > 1;
}

int main() {
    int n;
    cin >> n;
    cout << (isPrime(n) ? "Prime" : "Not a Prime");
}

3. Prime Factorization 🧩