Divisors & Primes

Now that we know how to mix numbers (GCD/LCM), let’s look inside a single number.

We want to answer two big questions efficiently:

  1. What numbers divide \(N\)? (Divisors)
  2. Is \(N\) a prime number?

If \(N\) is small (like 50), this is easy. If \(N\) is 1,000,000,000, doing it the wrong way will freeze your code.

The Big Idea: Square Root Optimization

This is the most important trick in basic Number Theory.

If you want to find factors of 36, let’s list them in pairs:

  • \(1 \times 36 = 36\)
  • \(2 \times 18 = 36\)
  • \(3 \times 12 = 36\)
  • \(4 \times 9 = 36\)
  • \(6 \times 6 = 36\) <– The Turning Point (\(\sqrt{36}\))
  • \(9 \times 4 = 36\) <– Repeat! We already saw {4, 9}
  • \(12 \times 3 = 36\) <– Repeat!
  • \(18 \times 2 = 36\) <– Repeat!
  • \(36 \times 1 = 36\) <– Repeat!

The Insight: Factors always come in pairs. If \(a \times b = N\), and \(a\) is small, then \(b\) must be big. They “meet” exactly at \(\sqrt{N}\).

Rule: You never need to check numbers bigger than \(\sqrt{N}\). If you haven’t found a factor by then, it doesn’t exist (or you already found its partner).

Finding Divisors

Goal: Print all divisors of a number \(N\).

The Slow Way

Loop from 1 to \(N\). Complexity: \(O(N)\)

// If N = 10^9, this takes ~10 second (too slow for many problems)
for (int i = 1; i <= n; i++) {
    if (n % i == 0) cout << i << " ";
}

The Optimized Way

Loop from 1 to \(\sqrt{N}\). When you find a divisor \(i\), you automatically find its partner \(\frac{n}{i}\). Complexity: \(O(\sqrt{N})\).

#include <iostream>
#include <vector>
#include <algorithm> // for sort
using namespace std;

int main() {
    long long n = 36;
    vector<long long> divisors;

    // Notice: i * i <= n is better than i <= sqrt(n)
    // It avoids slow floating-point math.
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i); // Add the small one
            
            // Add the big partner, but ONLY if they are different
            // (Check to avoid adding 6 twice for n=36)
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }

    // Note: The list won't be sorted (e.g., 1, 36, 2, 18...)

    for (long long d : divisors) cout << d << " ";
}

Prime Numbers

A Prime Number is a number greater than \(1\) that has exactly two divisors: 1 and itself.

Primality Test (Is \(N\) prime?)

Using the logic above: To prove a number is prime, we just need to verify it has no factors up to \(\sqrt{N}\).

bool isPrime(long long n) {
    if (n <= 1) return false; // 0 and 1 are not prime
    
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false; // Found a divisor! Not prime.
        }
    }
    return true; // Survived the loop? It's prime.
}

Example Problems

The Marching Band Formation

The Marching Band Formation

A high school marching band has 240 members. The band director wants to arrange the members into a rectangular formation for a parade. However, there are specific constraints for the formation:

  • All members must be included in the formation.
  • The formation must be a solid rectangle (no empty spots).
  • There must be at least 10 rows.
  • There cannot be more than 20 rows.

How many different rectangular formations satisfy these conditions?

Solution

To solve this, we need to find the divisors of 240. Since we are looking for pairs (Rows \(\times\) Columns = 240), we can use the square root method to find the pairs efficiently.

int findDivisors(int n) {
    vector<pair<int, int>> divisors;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (i * i == n) {
                divisors.push_back({i, i});
            } else {
                divisors.push_back({i, n/i});
                divisors.push_back({n/i, i}); // Add both combinations of i and n/i
            }
        }
    }

    int count = 0;
    for (int i = 0; i < (int)divisors.size(); ++i){
        if (divisors[i].first >= 10 && divisors[i].first <= 20){
            count++;
        }
    }

    return count;
}

If \(N=240\), the function finds \(5\) solutions. These are: - \(10\), \(24\) - \(12\), \(20\) - \(15\), \(16\) - \(16\), \(15\) - \(20\), \(12\)

T-Prime

T-Prime

We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we’ll call a positive integer \(t\) Т-prime, if \(t\) has exactly three distinct positive divisors.

You are given an array of \(n\) positive integers. For each of them determine whether it is Т-prime or not.

Solution

It can be shown that only squares of prime numbers are T-primes, and that there are not too many of them. Why?

If we had two prime factors \(p\), \(q\) of a number \(t\), then it would be divisible by at least \(p\), \(q\), \(pq\), \(1\) - which is more than \(3\). Then, it must be a power of a prime number. You can easily see now that \(t = p\) or \(t = p^3\) and higher, doesn’t really work.

int n;
cin >> n;

for (int i = 0; i < n; ++i){
    int x;
    cin >> x;

    int y = sqrt(x);
    if (y * y != x){
        cout << "NO\n";
        continue; //check whether x is a perfect square
    }

    if (isPrime(y))
        cout << "YES\n";
    else
        cout << "NO\n"; 
}