求所有质因子(Java)

求所有质因子(Java),第1张

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

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/web/2990438.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-09-23
下一篇2022-09-23

随机推荐

  • 什么叫刺身?

    刺身就是指鱼生之类的东西,指将新鲜的鱼贝类生切成片,蘸调味料直接食用的菜品。生鱼片为世界多地起源,日本古代为渔猎加农耕文化,有传统生食习惯,《东夷列传-倭国传》记载倭人生食海物,即生鱼片。生鱼片在中国古代是常见的鱼类菜品,后来在古代逐渐

  • 体前屈如何炼?

    1、静力性方法:身体保持某种姿势缓慢、均匀地拉伸几十秒或是更长的时间。即是常说的压腿、耗腿等方法。举例如: 1)压腿:有正压腿、侧压腿等各种方向的压腿。 正压腿是面对肋木或一定高度的物体,一腿支撑,另一腿脚跟放在肋木上,脚尖勾起,支撑腿脚尖

    2023-02-03
    100
  • 喷点菠萝鱼怎么养?

    菠萝成鱼相对不易患病,但是饲养时也很重要,要注意一些问题,否则难以养出好品相的菠萝 。一是水质。大菠萝对水质适应能力较强,不像鹦鹉要求那么高,但是也要注意保持它喜欢的水质才会养出色泽黄艳的鱼,大菠萝喜欢弱酸性软水,同鹦鹉,注意不要用碱性或硬

    2023-02-03
    200
  • 经济订货批量公式是什么?

    经济订货批量=√2×每次订货变动成本×存货年需要量÷单位存储变动成本。经济批量下,存货的相关总成本=√2×每次订货变动成本×存货年需要量×单位存储变动成本。最佳订货次数=存货年需要量÷经济订货批量。最佳订货期=360÷最佳订货次数。

    2023-02-03
    100
  • 上海地铁末班车是几点??

    上海地铁末班车是:最晚停运时间为22:31。一号线05:30到22:30,二号线5:49到22:24,三号线05:25到22:30,四号线05:30到22:30,五号线06:00到22:23,六号线6:08到21:26,七号线5:30到22

    2023-02-03
    100
  • 女朋友来大姨妈怎么办?

    1、首先,女朋友来大姨妈前你要多买些牛奶等含蛋白质的食物给她吃,不然到姨妈来之后你女朋友会出现脾气上升、肚子疼、头疼、头晕等症状,这样子会让你女朋友的身体变差,她对你的态度也会越来越差。2、对来大姨妈的女朋友说话要温柔,不要干那些事,要多关

  • 小说人物形象的作用 有什么用处

    在做小说阅读理解的时候,我们经常会遇到人物形象分析的题目,那么,小说中人物形象的作用都有哪些呢?小说艺术效果怎么分析 一、主要人物的作用 主要人物的作用,应从三个方面分析概括:表现主题+推进情节+体现社会意义。

    2023-02-03
    100
  • 盘是什么意思

    盘包浆的意思是文物表面由于长时间氧化形成的氧化层,为古玩行业专业术语。盘包浆就是文物的油脂渗出接触空气后,在木头表面形成的固化层,再经一定频率的盘玩把摩,使油脂混合体固化层均匀分布于珠串表面各部位,达到所谓的镜面效果。包浆其实就是光泽,专指

    2023-02-03
    100
  • bgm是什么意思

    BGM是背景音乐Backgroundmusic的意思,简称BGM。背景音乐通常是指在电视剧、电影、电子游戏和网站中用于调节气氛的一种音乐,插入于对话之中,能够增强情感的表达,达到一种让观众身临其境的感受。另外,在一些如酒吧、咖啡厅、商场等公

    2023-02-03
    100

发表评论

登录后才能评论

评论列表(0条)

    保存