Prime

Theorems

Euclid-Euler Theorem

The Euclid-Euler theorem relates perfect numbers to Mersenne primes. It states that an even number is perfect if and only if it has the form \(2^{p−1}(2^p − 1)\), where \(2^p − 1\) is a prime number.

Relatively Prime

Integers \(a\) and \(b\) are relatively prime iff there exists Bézout’s identity \(ax + by = 1\).

Algorithm

Count Primes

Sieve of Eratosthenes

public int countPrimes(int n) {
    boolean[] notPrime = new boolean[n];
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!notPrime[i]) {
            count++;
            for (int j = i; i * j < n; j++) {
                notPrime[i * j] = true;
            }
        }
    }
    return count;
}

• Time complexity: O(nlog(log(n)))
• Space compolexity: O(n)

Proof: Divergence of the Sum of the Reciprocals of the Primes

Prime Factorization

Shor’s algorithm: a polynomial-time quantum computer algorithm for integer factorization.

General number field sieve (GNFS): the most efficient classical algorithm known for factoring integers larger than \(10^{100}\)

GCD Sort of an Array

public boolean gcdSort(int[] nums) {
    // minPrims[i]: min prime factor of number i
    int[] minPrimes = sieve(Arrays.stream(nums).max().getAsInt() + 1);

    for (int num : nums) {
        for (int p : primeFactorization(num, minPrimes)) {
            union(num, p);
        }
    }

    int n = nums.length;
    int[] sorted = Arrays.copyOf(nums, n);
    Arrays.sort(sorted);

    for (int i = 0; i < n; i++) {
        if (find(nums[i]) != find(sorted[i])) {
            return false;
        }
    }
    return true;
}

private int[] sieve(int n) {
    int[] minPrimes = IntStream.range(0, n).toArray();

    for (int i = 2; i * i < n; i++) {
        if (minPrimes[i] == i) {
            for (int j = i * i; j < n; j += i) {
                if (minPrimes[j] > i) {
                    minPrimes[j] = i;
                }
            }
            // If minPrimes[i] == i after exiting the loop,
            // i is a prime
        }
    }

    return minPrimes;
}

private List<Integer> primeFactorization(int n, int[] minPrimes) {
    List<Integer> list = new ArrayList<>();
    while (n > 1) {
        list.add(minPrimes[n]);
        n /= minPrimes[n];
    }
    return list;
}

2 Keys Keyboard

public int minSteps(int n) {
    int s = 0;
    for (int d = 2; d <= n; d++) {
        while (n % d == 0) {
            s += d;
            n /= d;
        }
    }
    return s;
}

Integer Break

public int integerBreak(int n) {
    if (n < 4) {
        return n - 1;
    }

    int prod = 1;
    // if the maximum product contains a factor f >= 4
    // then we can replace it with factors 2 and (f - 2) without losing optimality
    // as 2 * (f - 2) = 2 * f - 4 >= f
    // we never need a factor >= 4
    // i.e. we only need factors 1, 2 and 3
    //
    // 1 is wasteful
    // 3 * 3 > 2 * 2 * 2, so we never use 2 more than twice.
    while (n > 4) {
        prod *= 3;
        n -= 3;
    }
    return prod * n;
}

Consecutive Numbers Sum

public int consecutiveNumbersSum(int n) {
    // (a + a + (k - 1)) * k / 2 = n
    // a = n / k - (k - 1) / 2
    //
    // a is an integer, so
    // n % k == 0 && k % 2 == 1

    // count of odd factors of n

    // discards all factor 2's
    while (n % 2 == 0) {
        n /= 2;
    }

    // 1 is always valid
    int count = 1;
    for (int k = 3; k * k <= n; k += 2) {
        // count of this factor
        int f = 0;
        while (n % k == 0) {
            n /= k;
            f++;
        }
        count *= f + 1;
    }

    // say k', n' are right before the last iteration starts
    // and k, n are after the loop ends
    // - if n == 1,
    //     - k' * k' <= n'
    //     - k * k > n
    //     - k' is the last prime factor and it's counted
    // - else,
    //     - k' * k' > n'
    //     - k == k', n == n'
    //     - n (n') is the last prime factor and it's not counted yet
    return n == 1 ? count : count * 2;
}