CSDN话题挑战赛第2期
参赛话题:算法题解
1.题目描述
一个合数可以表示成若干个质数相乘的形式,比如21=3×7,18=2×3×3,这些质数被称为它的质因子。2.题目链接
给定一个合数n(n≤2^31-1),求出它的所有质因子。
格式
输入格式
输入只有一行,就是一个正整数n
输出格式
输出一行,n所有的质因子,中间用空格分隔,质因子必须按照升序排列
样例
输入样例
30
输出样例
235
172.22.114.1963.思路讲解
从i = 2开始进行循环,如果n除以 i 余数为0,则继续除以i ,直到 n % i 不等于0。然后i++,一直到i = n结束。4.代码
因为一个素数乘以一个合数不可能是一个合数,所以每次i++不需要再判断 i 是否为素数,能整除的只能是素数。
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-0for(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
【Java|求所有质因子(Java)】
5000
2 2 2 5 5 5 5
345678
2 3 17 3389
推荐阅读
- 随想随写|归并排序(MergeSort)
- c++|P5661 [CSP-J2019] 公交换乘
- 剑指offer第二版|剑指offer 44. 从1到n整数中1出现的次数
- 并发CAS机制你真的理解了嘛((深入到操作系统分析))
- c++|Codeforces 693 D. Even-Odd Game
- 刷题记录|力扣周赛310场题解
- Leetcode|Leetcode989: 数组形式的整数加法 (简单题)python3
- Java基础|Java8 -- Lambda表达式
- Java并发编程 - 线程