Ints.java

package io.github.chermehdi.lib.math;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Ints {

  public static final int INF = Integer.MAX_VALUE >> 1;

  public static List<Integer> generatePrimeFactors(int n) {
    List<Integer> ret = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
      while (n % i == 0) {
        ret.add(i);
        n /= i;
      }
    }
    if (n > 1) {
      ret.add(n);
    }
    return ret;
  }


  public static int gcd(int a, int b) {
    if (b != 0) {
      return gcd(b, a % b);
    }
    return a;
  }

  public static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
  }

  public static int powMod(int base, int power, int Mod) {
    base %= Mod;
    int res = 1;
    while (power != 0) {
      if ((power & 1) != 0) {
        res = (res * base) % Mod;
      }
      base = (base * base) % Mod;
      power >>= 1;
    }
    return res;
  }

  public static int binPow(int a, int n) {
    int res = 1;
    while (n > 0) {
      if ((n & 1) != 0) {
        res *= a;
        --n;
      } else {
        a *= a;
        n >>= 1;
      }
    }
    return res;
  }

  public static long binPow(long a, long n) {
    long res = 1;
    while (n > 0) {
      if ((n & 1) != 0) {
        res *= a;
        --n;
      } else {
        a *= a;
        n >>= 1;
      }
    }
    return res;
  }

  public static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }
    if (n <= 3) {
      return true;
    }
    if ((n % 2) == 0 || (n % 3) == 0) {
      return false;
    }
    for (int i = 5; i * i <= n; i += 6) {
      if ((n % i) == 0 || (n % (i + 2)) == 0) {
        return false;
      }
    }
    return true;
  }

  int legendre(int n, int p) {
    int sum = 0;
    while (n != 0) {
      n /= p;
      sum += n;
    }
    return sum;
  }

  ArrayList<Integer> seive(int n) {
    boolean[] tab = new boolean[n + 1];
    for (int i = 2; i * i <= n; i++) {
      if (!tab[i]) {
        for (int j = i * 2; j <= n; j += i) {
          tab[j] = true;
        }
      }
    }
    ArrayList<Integer> ret = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
      if (!tab[i]) {
        ret.add(i);
      }
    }
    return ret;
  }

  long factorialDivisors(long n) {
    ArrayList<Integer> primes = seive((int) n);
    long res = 1L;
    for (int i = 0; i < primes.size(); i++) {
      long ans = primes.get(i);
      int exp = 0;
      while (ans <= n) {
        exp += (n / ans);
        ans *= primes.get(i);
      }
      res *= (exp + 1);
    }
    return res;
  }

  /**
   * generates an array containing prime numbers less than or equal to n
   *
   * @param n prime numbers limit
   * @return resulting prime numbers
   */
  public static int[] generatePrimesLinear(int n) {
    int[] lastPrime = new int[n + 1];
    int[] primes = new int[n + 1];
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
      if (lastPrime[i] == 0) {
        lastPrime[i] = i;
        primes[cnt++] = i;
      }
      for (int j = 0; j < cnt && primes[j] <= lastPrime[i] && i * primes[j] <= n; ++j) {
        lastPrime[i * primes[j]] = primes[j];
      }
    }
    return Arrays.copyOf(primes, cnt);
  }

  public static int[] lowestPrimeFactor(int n) {
    int[] lowest = new int[n + 1];
    int[] primes = new int[n + 1];
    int cnt = 0;
    for (int i = 2, pr; i <= n; ++i) {
      if (lowest[i] == 0) {
        lowest[i] = i;
        primes[cnt++] = i;
      }
      for (int j = 0; j < cnt && primes[j] <= lowest[i] && (pr = i * primes[j]) <= n; ++j) {
        lowest[pr] = primes[j];
      }
    }
    return lowest;
  }

  public static int phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) {
        while (n % i == 0) {
          n /= i;
        }
        res -= res / i;
      }
    }
    if (n > 1) {
      res -= res / n;
    }
    return res;
  }

  public static List<Integer> divisors(int a) {
    List<Integer> result = new ArrayList<>();
    for(int i = 1; i * (long) i <= a; ++i) {
      if(a % i == 0) {
        result.add(i);
        if(a / i != i) {
          result.add(a / i);
        }
      }
    }
    return result;
  }
}