HJ6 质数因子

怼烎@ 2024-03-27 16:05 35阅读 0赞

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ]  
> [牛客在线编程算法篇【题号NC开头】][NC]  
> [剑指offer【题号 JZ开头】][offer_ JZ]  
> [力扣][Link 1]

### 1）[原题链接][Link 2] ###

### 2）[已有题解][Link 3] ###

### 3）代码 ###

package math;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.stream.Collectors;
    
    import static java.lang.System.in;
    
    /**
     * HJ6 质数因子
     */
    public class HJ6PrimeFactor {
        
        public static void main(String[] args) throws IOException {
        
            BufferedReader bf = new BufferedReader(new InputStreamReader(in));
            Long num = Long.parseLong(bf.readLine());
            bf.close();
    
            List<Long> res = getPrimes(num);
    
            // 输出素数因子
            String str = res.stream().map(String::valueOf).collect(Collectors.joining(" "));
            System.out.println(str);
        }
    
        private static List<Long> getPrimes(Long num) {
        
            List<Long> res = new ArrayList<>();
    
            // Math.sqrt(num)两数相乘最大的也就是平方，再往后就是重复值了
            double sqrt = Math.sqrt(num);
            for (long i = 2L; i <= sqrt; i++) {
        
                while (num % i == 0) {
        
                    res.add(i);
                    num = num / i;
                }
            }
    
            // num==1说明全部整除开了，num!=1说明余下本身为素数
            if (num != 1) {
        
                res.add(num);
            }
            return res;
        }
    }

[HJ]: https://www.nowcoder.com/exam/oj/ta?tpId=37
[NC]: https://www.nowcoder.com/exam/oj
[offer_ JZ]: https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
[Link 1]: https://leetcode.cn/problemset/all/
[Link 2]: https://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607?tpId=37&tqId=21229&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=/exam/oj/ta?tpId=37&difficulty=undefined&judgeStatus=undefined&tags=&title=
[Link 3]: https://juejin.cn/post/7101835806800609293