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 givenn
is Prime Number (质数) - For
i<=Math.sqrt(n)
, see Factor Maximum Value