黑马程序员技术交流社区

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

作者: Cfan_yang    时间: 2014-12-9 21:25
标题: 分解质因数。
  1. import java.util.*;

  2. public class ZhiYinShu {
  3.     public static void main(String args[]) {
  4.         Scanner sc = new Scanner(System.in);
  5.         System.out.print("请输入一个正整数:");
  6.         int num = sc.nextInt();
  7.         System.out.print(num + "=");
  8.         for (int i = 2; i <= num;) {
  9.             if (num == i) {
  10.                 System.out.println(i);
  11.                 break;
  12.             } else if (num % i == 0) {
  13.                 System.out.print(i + "*");
  14.                 num = num / i;
  15.             } else {
  16.                 i++;
  17.             }
  18.         }
  19.     }
  20. }
复制代码
这是一个分解质因数的程序。
程序中是如何确保变量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