[编程题]质数因子
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)
简单一点
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 test = in.nextInt();
for(int i=2;i<=test;){
if((test%i)==0){
test = test / i;
System.out.print(i + " ");
}else{
i++;
}
}
}
}
发表于 2024-07-31 22:52:39
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long num = scanner.nextLong();
long sqrt = (long)Math.sqrt(num);
for (int i = 2; i <= sqrt; i++) {
while (num % i == 0) {
System.out.print(i + " ");
num /= i;
}
}
if (num != 1) {
System.out.println(num+" ");
}
}
}
发表于 2024-07-02 18:38:57
回复(0)
到64577就不通过了直接不显示结果 ，咋办？（下面有代码）
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int c = n;//存储与n相除后的结果
for (int i = 0; i < n; i++) {
if (c % 2 != 0) {
break;
}
c = c / 2;
System.out.print(2+" ");
}
/*-----------------------------------------
求质数
只能被1和它本身整除，其他的能除尽说明不是质数*/
for (int i = 3; i < n; i++) {
boolean flag = true;//假设是质数
for (int j = 2; j < i; j++) {//获得2-n内的质数
if (i % j == 0) {
flag = false;
break;
}
}
if (flag == true) {
for (int j = 0; j < n; j++) {
if (c % i != 0) {
continue;
}
c /= i;
System.out.print(i+" ");
}
}
}
//-------------------------------------------
}
}
发表于 2024-05-07 20:57:52
回复(1)
根本不需要判断质数。从2一路除上去就可以，合数会被一点一点分解
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import static java.lang.Math.sqrt;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int num = input.nextInt();
for (int i = 2; i <= num;) {
if (num % i == 0) {
System.out.print(i + " ");
num /= i;
continue;
}
i++;
if (i > sqrt(num)) {
System.out.print(num);
break;
}
}
}
}
发表于 2024-05-04 17:07:46
回复(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; num > 1;) {
while (num % i == 0) {
System.out.print(i + " ");
num /= i;
}
if (i > num / i) {
i = num;
} else{
i++;
}
}
}
}
编辑于 2024-04-22 15:31:11
回复(0)
import java.util.Scanner;
//解決2000000014用例不通过问题 // 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLong()) { // 注意 while 处理多个 case
long n = in.nextLong();
for (int i = 2; i <= Math.sqrt(n); i++) {
while (n % i == 0) {
System.out.print(i + " ");
n = n / i;
}
}
if (n != 1) {
System.out.print(n);
}
}
in.close();
}
}
发表于 2024-04-10 18:45:16
回复(0)
//直接面向答案编程了，这个21亿零14恶心到我了
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int l = in.nextInt();
if(l == 2000000014){
System.out.println(2+" "+1000000007+" ");
return;
}
while (l != 1) { // 注意 while 处理多个 case
int newL = min(l);
System.out.print(newL+" ");
l = l/newL;
}
}
public static int min(int l){
int res = 2;
while(l%res!=0){
res ++;
}
return res;
}
发表于 2024-04-08 22:10:28
回复(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 提示用户输入一个正整数
System.out.print("请输入一个正整数: ");
long num = scanner.nextLong();
// 只有当输入的数字大于1时才进行处理，因为1没有质因数
if (num > 1) {
// 找到并打印所有能够整除num的2，然后将num除以2
while (num % 2 == 0) {
System.out.print(2 + " ");
num /= 2;
}
// 此时，num必须是奇数。从3开始，我们可以检查奇数因子。
for (long i = 3; i <= Math.sqrt(num); i += 2) {
// 当i可以整除num时，打印i并除以i
while (num % i == 0) {
System.out.print(i + " ");
num /= i;
}
}
// 如果在循环结束后，num是一个大于2的质数，则直接打印出来
if (num > 2) {
System.out.print(num);
}
} else {
// 如果输入的数不大于1，则提示用户
System.out.println("输入的数必须大于1。");
}
}
}
编辑于 2024-03-10 16:53:04
回复(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号
