黑马程序员技术交流社区

标题: 分解质因数。 [打印本页]

作者: Cfan_yang 时间: 2014-12-9 21:25
标题: 分解质因数。

import java.util.*;
public class ZhiYinShu {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入一个正整数：");
int num = sc.nextInt();
System.out.print(num + "=");
for (int i = 2; i <= num;) {
if (num == i) {
System.out.println(i);
break;
} else if (num % i == 0) {
System.out.print(i + "*");
num = num / i;
} else {
i++;
}
}
}
}

复制代码

这是一个分解质因数的程序。
程序中是如何确保变量i是质数的？

作者: 不淡定，小学生 时间: 2014-12-9 21:47
用一个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是质数，反之是质数。

作者: 提米特 时间: 2014-12-10 18:41
我帮你逐行加了注释，希望能帮你理解这个函数

分析：求质因数分解的原理是建立一个循环，遍历从2到待分解数之间的质数，每次遇到可以被原数整除的质数就不换行打印一次并加上”*“，这样遍历结束时打印的结果就是待分解数的质因数分解。

你问为什么i是质数，我这里看了一遍程序，i并不是质数，这个程序的想法是好的，但是由于i不是质数，所以最后无法实现分解质因数的功能，只能分解成不重复整数的乘积的形式。如果要实现分解成质因数的功能，需要在遍历时每次使用递增的质数来判断。

楼上不看代码回复我也是醉了，还有被加分我也是不知道管理员有没有看帖子。

import java.util.*;       //这一行是导入java自带的函数库，因为下面用到了Scanner读取用户输入

public class ZhiYinShu {
public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      System.out.print("请输入一个正整数：");
      int num = sc.nextInt();                               //这里定义了num用来储存用户想要分解质因数的数
      System.out.print(num + "=");
      for (int i = 2; i <= num;) {                         //这个for循环是用来遍历从2到num之间的每一个整数，i是用来存放当前遍历数值的变量，由于不是质数，                                                                               所以分解的结果是不重复的整数分解因式
         if (num == i) {                                     //如果待分解的数等于i的初值2，则没必要分解，直接打印2
            System.out.println(i);
            break;
         } else if (num % i == 0) {                   //如果待分解的数对i取余为0，则表示num含有因子i
            System.out.print(i + "*");                //不换行打印i和”*“
            num = num / i;                            //由于从num中取出了i这个因子，所以目前待分解的数需要除以i
         } else {
            i++;                                                 //如果num既不等于i也没办法整除i，则i自增1，换下一个数来判断是否是num的因子
         }
      }
}
}

作者: 提米特 时间: 2014-12-10 19:32
我重新实现了你要的功能，你可以参考一下

package com.ithema;
/*
* 这个类完成的功能是对用户输入的一个数进行质因式分解
* 有2个函数，zhiYinshu(int num)这个方法实现的是对给定数进行因式分解
* isZhiShu(int num)这个方法实现的是判断一个数是否为质数
* 这两个方法结合起来就可以较好地完成质因式分解的功能
* @author：zly
*/

import java.util.Scanner;

public class ZhiYinShu {

public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner input = new Scanner(System.in);
System.out.println("请输入您要分解的因式");
int n = input.nextInt();
zhiYinshu(n);
}
/*
   * 这个方法实现的功能是对给定数进行因式分解
   */
public static void zhiYinshu(int num)
{
if(isZhiShu(num)) //如果输入的数为质数，则质因数分解无意义
System.out.println("您输入的数为质数，无法被分解");
else
{
         System.out.print(num + "=");
         for (int i = 2; i <= num;) //遍历从2到待分解数之间的整数
         {
            if(isZhiShu(i)) //判断此时遍历的数是否为质数，是则继续，不是则i自增1再循环
            {
            if (num == i)
            {
                  System.out.println(i);
                  break;
            }
            else if (num % i == 0)
            {
                  System.out.print(i + "*");
                  num = num / i;
            }
            else if(num < i) //如果i遍历到比num大，说明num无法被i整除，即无法分解为质因数乘积的形式
            {
            System.out.println("此数无法分解为质因数的乘积");
            break;
            }
            else //这里是为了避免重复因子只被查找一次就跳过，比如4=2*2这种情况
            i++;
            }
            else //如果i当前不是质数，则自增1重新循环
            i++;
         }
}
}

/*
   * 这个方法来判断给定整数是否为质因数
   * 核心思想是遍历从2到该数之间的元素，判断是否能被其整除，如果有则表明该数不是质数
   */
public static boolean isZhiShu(int num)    //用来判断则返回值为布尔类型
{
boolean result = true;       //默认返回值为真
for(int i = 2 ; i < num ; i++)
{
if(num % i == 0)          //如果在2到num之间有一个数能被num整除，则num不是质数
{
result = false;
break;
}
}
return result;
}

}

作者: 提米特 时间: 2014-12-10 19:40
自己写完代码才发现，你给出的函数就可以很好地分解质因式。
我思考了一下原因，即使i不是质数，由于函数在不断从2开始尝试分解给定数字，所以首先不断除2，除不尽了再尝试3，下一个数会尝试4，但是在第一步中已经除尽了2，所以4就跳过了，下一个是5。。依次类推

i在这个过程中虽然不是质数，但是由于每一个合数都可以分解为质因数的乘积，我们在除某一个合数的时候，在此之间由于多次尝试会把它的因子全部都除尽，所以这个合数自然不会整除。也就是避免了合数在分解的过程中被打印出来。所以最终显示的结果一定是质因数的乘积。

不得不佩服想出这个算法的人，很厉害！

作者: Cfan_yang 时间: 2014-12-10 19:55

提米特发表于 2014-12-10 19:40
自己写完代码才发现，你给出的函数就可以很好地分解质因式。
我思考了一下原因，即使i不是质数，由于函数在 ...

谢啦！:lol

作者: 请叫我丶菜鸟 时间: 2014-12-10 21:31
class Prog4 { public static void main(String[] args) { int n=29; isMath(n);//调用 } //下面是分解质因数的功能（方法） static void isMath(int n)//n表示要被分解质因数的正整数 { int k=2; while(true) { if(n%k==0) //判断n除k是否能除尽，如果除不尽则 K 加 1 { System.out.println(k); n=n/k; //将n/k的值赋给n，作为下一次的除数 continue; } else k++; //如果n除不尽，就说明k不是质因数，取下一个值 if(n==1) //如果n==1成立，则说明 n=k，就退出 break; } } }

作者: 请叫我丶菜鸟 时间: 2014-12-10 21:34
本帖最后由请叫我丶菜鸟于 2014-12-10 21:38 编辑

class Prog4
  {
   public static void main(String[] args)
      {
               int  n=29;
               isMath(n);//调用
      }
               //下面是分解质因数的功能（方法）
      static void isMath(int n)//n表示要被分解质因数的正整数
      {
               int k=2;
            while(true)
               {
                     if(n%k==0)
                     //判断n除k是否能除尽，如果除不尽则 K 加 1
                     {
                              System.out.println(k);
                              n=n/k;             //将n/k的值赋给n，作为下一次的除数
                              continue;
                     }
                     else
                              k++;             //如果n除不尽，就说明k不是质因数，取下一个值
                     if(n==1)             //如果n==1成立，则说明 n=k，就退出
                           break;
            }
      }
}

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2