Factor

Abstract

---

• Also known as divisor
• A number that divides another number without leaving a remainder
• 1 is a factor for all Integer (整数)

Factor Maximum Value

• Factor maximum value <= square root of a given number, below is a visualisation. It is also know as Trial Division Method

Find Minimal Greater-than-One Factor

Find the minimal factor of a given integer that is >1

// Time Complexity - O(sqrt(n)), where n is the size of the integer
public static int minFactor(int n) {
  for (int i=2; i<=Math.sqrt(n); i++) {
    if (n%i == 0) return i;
  }
 
  // When we cant find factor that is bigger than 2 and smaller than n
  return n;
}

• If the function returns the given n, then the given n is Prime Number (质数)
• For i<=Math.sqrt(n), see Factor Maximum Value