Math

2523. Closest Prime Numbers in Range

class Solution {
public:
    vector<int> closestPrimes(int left, int right) {
        vector<int> flags(right+1, 1);
        flags[0] = 0;
        flags[1] = 0;

        for (int i = 2; i * i <= right; i++) {
            for (int j = i * i; j <= right; j = j + i) {
                flags[j] = 0;
            }
        }

        vector<int> result = {-1, -1};
        int min = INT_MAX;
        int l = -1;
        int r = -1;
        for (int i = left; i <= right; i++) {
            if (flags[i] == 1) {
                printf("i: %d\n", i);
                if (l == -1 && r == -1) {
                    l = i;
                    r = i;
                } else {
                    l = r;
                    r = i;
                    if (r - l < min) {
                        min = r - l;
                        result[0] = l;
                        result[1] = r;
                    }
                }
            }
        }
        return result;
    }
};

1979. Find Greatest Common Divisor of Array

GCD

1. Brute Force

2. Euclidean Division

3. Phase Reduction Technique

4. Combination of Phase Reduction Technique and Transposition

class Solution {
public:
    int findGCD(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int a = nums.front();
        int b = nums.back();
        return fast(a, b);
    }

private:
    int bruteForce(int a, int b) {
        for (int i = a; i > 1; i--) {
            if (a % i == 0 && b % i == 0) {
                return i;
            }
        }
        return 1;
    }

    int euclideanDivision(int a, int b) {
        if (b % a == 0) {
            return a;
        }
        return euclideanDivision(b % a, a);
    }

    int phaseReduction(int a, int b) {
        if (b % a == 0) {
            return a;
        }
        return phaseReduction(min(a, b-a), max(a, b-a));
    }

    int fast(int a, int b) {
        if (a == b) {
            return a;
        }
        if (a&1 == 0 && b&1 == 0) {
            return fast(a>>1, b>>1)<<1;
        } else if (a&1 == 0 && b&1 == 1) {
            return fast(a>>1, b);
        } else if (a&1 == 1 && b&1 == 0) {
            return fast(a, b>>1);
        } else {
            int big = a > b ? a : b;
            int small = a > b ? b : a;
            return fast(big - small, small);
        }
    }
};

204. Count Primes

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        vector<bool> flags(n, true);
        flags[0] = false;
        flags[1] = false;
        for (int i = 2; i * i < n; i++) {
            if (flags[i]) {
                for (long j = i * i; j < n; j = j + i) {
                    flags[j] = false;
                }
            }
        }

        int count = 0;
        for (int i = 2; i < n; i++) {
            if (flags[i]) {
                count++;
            }
        }
        
        return count;
    }
};