public class PrimeFactorsEffective {
public static List<Integer> primeFactors(int numbers) {
int n = numbers;
List<Integer> factors = new ArrayList<Integer>();
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) {
factors.add(n);
}
return factors;
}
Can Any one suggest me the most optimised code of prime factorisation which is used by most competitive programmer.
Time complexity is \mathcal{O}(\sqrt N) as you iterate until the following conditions is violated
i \le\frac{N}{i} \equiv i^2 \le N \equiv i \le \sqrt N
thanks