Java 优化最坏时间线性复杂度代码
质数因子
http://www.nowcoder.com/questionTerminal/196534628ca6490ebce2e336b47b3607
此题，如果代码的最坏时间复杂度是线性的，只能通过大概 91% 的样例（我使用 java 的测试结果），原因之所在就是会有超大素数作为特殊样例来恶心人：
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long num = scanner.nextLong();
for (long i = 2; i <= num; ++i) {
while (num % i == 0) {
System.out.print(i + " ");
num /= i;
}
}
System.out.println();
} 但是正如我们判断数 num 是不是质数时，没必要从 2 一直尝试到 num 一样，此题中的大循环也大可不必写一个到 num 的循环，写到 即可，如果此时数字还没有除数，则可判定其本身是一个质数，没有再除下去的必要了，直接打印其本身即可：
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long num = scanner.nextLong();
long k = (long) Math.sqrt(num);
for (long i = 2; i <= k; ++i) {
while (num % i == 0) {
System.out.print(i + " ");
num /= i;
}
}
System.out.println(num == 1 ? "": num+" ");
} 
阿里巴巴灵犀互娱公司福利 622人发布
查看17道真题和解析