分解质因数

题目如题

求一个数分解质因数，只要从最小的质数除起，一直除到结果为质数，所以按理说应该先找到比N小的全部质数。先看代码：

 1 import java.util.Scanner;
 2 public class test
 3 {
 4     public static void main(String [] args)
 5     {
 6         int m,n,i;
 7         Scanner scanner=new Scanner(System.in);
 8         System.out.printf("input a number n=:");
 9         n=scanner.nextInt();
10         m=n;
11         for(i=2;i<=n;i++)
12         {
13             if(n%i==0)
14             {   
15                 System.out.printf("%4d",i);
16                 n=n/i;
17                 i--; //如果已经找到了一个质数，继续判断此时的i是否还是余数的因子
18             }
19         }
20     }
21 }

显然不是把全部比N小的质数找出来再逐个判断，这里使用了短除法。下面说说短除法是怎样得到同样的结果的。

每当找到一个质数a的时候，总是判断余数是否还包含有质数a，否则继续判断下一个整数，如果它可以整除余数，那么它一定是一个质数。因为如果它是合数，那么它可以被前面的质数分解，但它的因子肯定在这之前都被找出来了。