求所有质因子（Java）

CSDN话题挑战赛第2期
参赛话题：算法题解

1.题目描述

一个合数可以表示成若干个质数相乘的形式，比如21=3×7，18=2×3×3，这些质数被称为它的质因子。
给定一个合数n(n≤2^31-1)，求出它的所有质因子。

格式

输入格式
输入只有一行，就是一个正整数n

输出格式
输出一行，n所有的质因子，中间用空格分隔，质因子必须按照升序排列

样例
输入样例
30
输出样例
2  3  5

2.题目链接

172.22.114.196

3.思路讲解

从i = 2开始进行循环，如果n除以 i 余数为0，则继续除以i ，直到 n % i 不等于0。然后i++，一直到i = n结束。

除此之外，每次i++不需要再判断 i 是否为素数，能整除的只能是素数。

4.代码

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = n,flag = 0;
 
        for(int i = 2;i <= m;i++) {
            if(n % i == 0) {
                while (n % i == 0) {
                    if(flag == 0) {
                        System.out.print(i);
                        flag = 1;
                    }
                    else {
                        System.out.print(" " + i);
                    }
                    n /= i;
                }
            }
        }
 
        scanner.close();
    }
}

5.感想

本题是一道很简单的算法题，难度不大。

但是我之前一直纠结于判断i是否为素数，采用了两种不同的方法。一次超时，一次超内存。

public class Test01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = n,flag = 0;
 
        for(int i = 2;i <= m;i++) {
            int isPrime = 1;
            for(int j = 2;j*j <= i;j++) {
                if(i % j == 0) {
                    isPrime = 0;
                    break;
                }
            }
            if(isPrime == 1 && n % i == 0) {
                //System.out.println("i = " + i + " n = "+ n);
                while (n % i == 0) {
                    if(flag == 0) {
                        System.out.print(i);
                        flag = 1;
                    }
                    else {
                        System.out.print(" " + i);
                    }
                    n /= i;
                }
            }
        }
 
        scanner.close();
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = n,flag = 0;
        int[] isPrime = new int[n+5];//prime-0
 
 
        for(int i = 2;i*i <= n;i++) {
            if(isPrime[i] == 0) {
                for(int j = 2;j*i < n+5;j++) {
                    isPrime[i*j] = 1;
                }
            }
        }
        isPrime[1] = 1;
        isPrime[2] = 0;
 
        for(int i = 2;i <= m;i++) {
            if(isPrime[i] == 0 && n % i == 0) {
                //System.out.println("i = " + i + " n = "+ n);
                while (n % i == 0) {
                    if(flag == 0) {
                        System.out.print(i);
                        flag = 1;
                    }
                    else {
                        System.out.print(" " + i);
                    }
                    n /= i;
                }
            }
        }
 
        scanner.close();
    }
}

这里再提供一些测试数据：

100
2 2 5 5

5000
2 2 2 5 5 5 5

345678
2 3 17 3389