Question

free pascal编程求2-100中每个数的质因子.

2=2
3=3
4=2*2
....
99=3*3*11
100=2*2*5*5；
且告诉我每一步的意思

Answer 1

这个简单。思路就是：一个大循环，i := 2 to 100 对每个数i作质数分解。 所以关键是对某个整数作分解。 以99这个数为例说明，除数先从最小的质数2开始，99不能被2整数，除数+1 = 3； 99可以被3整除，记录这个质数3， 然后99÷3=33后继续被3整数，又的得11，再次记录质数3； 这时11不能被3整数了，不用记录3， 那么除数+1=4； 11不能被4整除，继续除数+1=5，。。。，直到11，可以整除，记录11，剩余的数是1，过程结束。注意：结束的条件有两个，一是剩余的数=1；二是这个除数+1的过程直到除数＞99 div 2 = 44为止，这是因为假设n = a·b成立，a的最小质数取值范围是2，那么b的最大取值范围≤n÷2，因此超过范围的b取值，无意义，只是增加循环的次数而已。

代码如下：

...
var
  i : integer;
begin
  // 求2~100的每个数的因子
  for i := 2 to 100 do
    Writeln (IntToStr(i) + '=' + factorDecomp (i)); //调用因子分解函数，按格式输出。

end;
...          
function factorDecomp(const num : Integer) : String;
var
  sDF : String;
  nRest : Integer;
  nDivisor : Integer;
begin
  nDivisor := 2; //除数从2开始
  nRest := num; // num是需要分解的整数
  sDF := ''; //sDF是记录质数因子的字符串，格式： 2*2*5*5
  repeat     // 除数从2开始的循环
    while (nRest mod nDivisor = 0) do
    begin
         // 记录发现的因子。 如果是第1个发现的，直接记录；否则按*n这种方式记录。
         if length(sDF) = 0 then
           sDF := IntToStr(nDivisor)
         else
           sDF := sDF + '*' + intToStr(nDivisor);

         nRest := nRest div nDivisor; // 把分解剩下的数赋值给nRest，继续同一个因子的分解
    end;
    inc (nDivisor); //除数+1， 继续分解。
  until (nRest = 1) or (nDivisor > num div 2); //结束条件，余下的数=1或除数超过num的一半

  if length(sDF) = 0 then  //如果没有输出，那么该数无法分解，记录该数即可
    sDF := IntToStr(num);

  Result := sDF; //返回最后的结果，格式： n或者n1*n2*n3...
end;

追问

可不可以用简单一点的方法啊

我还没学到那儿啊

追答

谢谢肯定。 就整数的质因子分解而言，这个已是最简单的方法了，其他大都涉及到比较复杂的数学理论， 这个就是循环试除，相对而言，比较费时，太实现简单。 有不明白的地方，说出来一起探讨。

追问

那个太难理解了

老师说直接用循环就行了

根本不用那个什么function

追答

用函数不是必须的，主要是为了把计算和输出分开。 这时程序设计的好习惯。

追问

那可以用循环吗

谢谢

追答

当然可以。事实上，上面的例子已经用了啊。

1. 主程序里面， 用了  for i := 2 to 100 do

2. 子程序里面用了 repeat .. until， 里面还嵌套了一个while ... do

你要是把真正求解因子的函数里面的两个循环，放到主程序的for循环里面，也是可以的。但还是那句话，模块化是程序的基本构成，然后才是结构化，面向对象什么的。 正确使用函数，是一个好习惯。