题解 | #质数因子#

质数因子

http://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607

这个问题大部分的解法都是这样,利用循环穷举。

Scanner scanner = new Scanner(System.in);

long num = scanner.nextLong();
while(num != 1)
{
            for (int i = 2; i <= num; ++i) {
                if (num % i == 0) {
                    System.out.print(i + " ");
                    num /= i;
                    break;
                }
            }
}

也不能说错,但是这个方法遇到大数就过不了。
所以要怎么优化呢?
1.降低循环次数,利用Math.sqrt

long k = (long) Math.sqrt(num);

2.利用双重循环,假如输入的数值能被2整除,那就一直整除下去

for (long i = 2; i <= k; ++i) {
            while (num % i == 0) {
                System.out.print(i + " ");
                num /= i;
            }
}

3.最后再判断除完的数有没有大于1

System.out.println(num == 1 ? "": num+" ");

那么最终的解法是

import java.util.Scanner;

public class Main {
    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+" ");
    }
}
全部评论

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务