[编程题]质数因子
java方法解决超时问题，且时间复杂度为N，优化了解题的N2。
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long a = in.nextInt();
long up = (long) Math.sqrt(a);
String str = "";
for (int i = 2; i <= up;) {
if (a % i == 0) {
a = a / i;
System.out.print(i + " ");
str = str +i+" ";
} else {
i++;
}
}
System.out.println(a == 1 ? "": a+" ");
}
发表于 2025-08-26 16:39:51
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int i = 2;
while(i <= Math.sqrt(n)) {
if (n % i == 0) {
System.out.print(i + " ");
n = n / i;
i = 2;
} else {
i++;
}
}
System.out.print(n);
in.close();
}
}
发表于 2025-06-15 19:38:18
回复(0)
参考了别人的循环次数k=Math.sqrt(num)，稍微改了一下
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int num = in.nextInt();
int temp = num;
long k = (long)Math.sqrt(num);
long num2 = 1;
for (int i=2;i<=k;i++) {
while (temp % i == 0) {
System.out.print(i+" ");
temp = temp / i;
num2 *= i;
}
}
System.out.print(num == 1 ? "": (num/num2 == 1 ? " " : num/num2) + " ");
}
}
发表于 2025-05-30 22:09:35
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
while (num % 2 == 0) {
System.out.print(2 + " ");
num /= 2;
}
for (int i = 3; i <= Math.sqrt(num);) {
if (num % i == 0) {
System.out.print(i + " ");
num /= i;
} else {
i += 2;
}
}
if (num > 2) {
System.out.print(num + " ");
}
}
@凌十羽，改进一下，运行时间更快
发表于 2025-05-30 16:30:54
回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
//暴力求解了，有一组数据没有通过，很遗憾，想看看大佬们怎么写的
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long hex = 0L;
while (scanner.hasNextInt()) {
hex = scanner.nextInt();
List<Long> list = convert(hex);
StringBuilder result = new StringBuilder();
for (Long aLong : list) {
result.append(aLong).append(" ");
}
System.out.println(result.toString().trim());
}
}
public static boolean isPrime(long hex) {
if (hex > 3) {
for (long i = 2; i * i < hex + 1; i++) {
if (hex % i == 0) {
return false;
}
}
}
return true;
}
public static List<Long> convert(long hex) {
List<Long> list = new ArrayList<>();
long i = 2;
long temp = hex;
while (i <= temp) {
if (!isPrime(i)) {
i++;
continue;
}
if (temp % i == 0) {
list.add(i);
temp /= i;
} else {
i++;
}
}
if (list.isEmpty()) {
list.add(hex);
}
return list;
}
}
发表于 2025-03-12 13:31:22
回复(1)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
while (num % 2 == 0){
System.out.print(2 + " ");
num /= 2;
}
for(int i = 3;i <= num;){
if(num % i == 0){
System.out.print(i+" ");
num /= i;
}
else{
i += 2;
}
}
}
} 单位为1的自增速度太慢，3及以后的都是奇数，自增最小单位改为2，优化时间
发表于 2024-11-27 00:52:42
回复(0)
Java版本，用时37ms
import java.util.Scanner;
import java.util.*;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// System.out.println("请输入您要分解的数");
int decomposed = sc.nextInt();
List<Integer> factors = getFactors(decomposed);
StringBuilder sb = new StringBuilder();
for (Integer factor : factors) {
sb.append(factor).append(" ");
}
System.out.println(sb.toString());
}
private static List<Integer> getFactors(int decomposed) {
List<Integer> factors = new ArrayList<>();
// 计算2是否在其中
while (decomposed % 2 == 0) {
factors.add(2);
decomposed /= 2;
}
// 计算奇数的质因子
for (int i = 3; i <= Math.sqrt(decomposed); i = i + 2) {
while (decomposed % i == 0) {
factors.add(i);
decomposed /= i;
}
}
// 如果decomposed是质数而且大于2
if (decomposed > 2) {
factors.add(decomposed);
}
return factors;
}
}
发表于 2024-09-12 15:54:55
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
for(int i = 2;i <= num;){
while(num%i==0){
System.out.print(i+" ");
num /= i;
}
i++;
}
}
}
发表于 2024-09-12 11:54:55
回复(2)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int limit = in.nextInt();
for (int i = 2; i * i <= limit; i++) {
if (limit % i == 0) {
limit = limit / i;
System.out.print(i + " ");
i = i - 1;
}
}
System.out.print(limit);
}
}
发表于 2024-09-11 20:41:53
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int a = in.nextInt();
for (int i=2; i<=a; i++) {
while (a%i == 0) {
System.out.print(i + " ");
a /= i;
}
}
}
}
}
发表于 2024-09-06 14:15:35
回复(1)
知识点：唯一分解定理；n中最多只能有一个大于根号n的因子；分解质因数：试除法。
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int number = in.nextInt();
decompose(number);
}
public static void decompose(int num) {
Map<Integer, Integer> map = new TreeMap<>();
int len = num;
// 质因子的范围是2~根号n
for(int i = 2; i * i <= len; i++) {
while(num % i == 0) {
map.put(i, map.getOrDefault(i, 0) + 1);
num /= i;
}
}
if(num > 1) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 遍历并按照 key 从小到大打印，每个 key 打印 value 次
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
// 打印 key 对应的 value 次
for (int i = 0; i < value; i++) {
System.out.print(key + " ");
}
}
}
}
发表于 2024-09-05 21:50:58
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static int f(int x){
if(x==1){
return 1;
}else{
for(int i=2;i<=x;i++){
if(x%i==0){
System.out.print(i+" ");
return f(x/i);
}
}
}
return 1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m=in.nextInt();
f(m);
}
}
发表于 2024-09-05 10:02:48
回复(0)
import java.util.Scanner;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLong()) {
long num = in.nextLong();
if(num <= 3){
System.out.println(num);
return;
}
long startTime = System.currentTimeMillis();
// 分解 2 的幂次
while (num % 2 == 0) {
System.out.print(2 + " ");
num /= 2;
}
// 分解奇数质因子
for (long i = 3; i <= Math.sqrt(num); i += 2) {
while (num % i == 0) {
System.out.print(i + " ");
num /= i;
}
}
// 如果 n 是一个大于 2 的质数
if (num > 2) {
System.out.print(num);
}
}
}
}
发表于 2024-08-16 22:10:27
回复(0)
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(bf.readLine());
Main main = new Main();
main.print(num, 2);
}
public void print(int num, int start) {
for (int i = start; i <= num/start; i++) {
if (num % i == 0) {
System.out.print(i + " ");
num /= i;
print(num, start);
break;
}
if (num/start <= i) {
System.out.print(num);
return;
}
}
}
}
发表于 2024-08-13 12:36:49
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
StringBuilder res = new StringBuilder();
int i = 2;
while(i < a){
if(a % i == 0){
res.append(i + " ");
a /= i;
}else{
i++;
}
}
res.append(i + " ");
System.out.println(res);
}
}
发表于 2024-08-11 14:02:11
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-07 20:23:25 -
2023-02-02 23:55:15
-
2023-01-24 12:08:15 -
2023-01-07 14:37:29 -
2022-12-02 16:24:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
