求N的不同因数的个数

大榕树 \ Pascal语言 \ Pascal入门

求N的不同因数的个数

原文链接：http://www.mydrs.org/program/list.asp?id=313
一、问题描述
    任给一个自然数，求出这个自然数不同因数的个数 m。
二、问题分析
    下面列举出若干个 n 和 m 的值先看一看：
    n= 1 2 3 4 5 6 7 8 ……
    m= 1 2 2 3 2 4 2 4 ……
    显然，自然数 1 处于特殊地位；任何素数(大于 1，只有 1 和自己为自然数的因数)的因数个数都是 2；合数的因数个数 >2，究竟多大则较难寻找出规律来。为此，可以通过试除法来求出 m。
三、算法设计
    当 n=1时 m=1，是特例：
    其他情况的处理如下：
    m:=2;
    for i:=2 to k do
      if n mod i=0 then m=m+2
    其中
      k:=trunc(sqrt(n))
这里取 m=m+2 是因为如果发现 n 的一个小于 √n 的因数，必然同时有一个大于 √n 的因数。但对于 n 正好是完全平方数时，上述的 m 应减去 1。
四、程序设计
程序中根据输入的 n，输出因数个数 m。
五、程序清单
Pascal
PROGRAM e102-1；
VAR
    n, i, j, k: longint;
    m: integer;
BEGIN
REPEAT
    write('Input N=');
    readln(n);
    IF n<=0 THEN writeln('N>0!!')
UNTIL n>0
IF n=1 THEN writeln('N=',1:10,'M=',1)
ELSE BEGIN
    j:=n;
    m:=2;
    K:=trunc(sqrt(j));
    FOR i:=2 to k DO
      IF j MOD i =0 THEN m:=m+2;
    IF j=sqr(k) THEN m:=m-1
    witeln('N=',j:10,'M=',m);
END
END.
QBASIC:
CLS
DO
INPUT "N=", n
IF n > 0 THEN
    EXIT DO
ELSE
    PRINT "N>0!!"
END IF
LOOP
IF n = 1 THEN
PRINT "N="; n, "M="; 1
ELSE
m = 2
k = INT(SQR(n))
FOR i = 2 TO k
    IF n MOD i = 0 THEN m = m + 2
NEXT
IF SQR(n) = INT(SQR(n)) THEN m = m - 1
PRINT "N="; n, "M="; m
END IF
END
问题扩展：　
    对自然数 n 作素因数分解。
    ① n 为素数时    n=1*n   (n>1)
    ② n 为合数时    n=p₁^a1*p₂^a2*p_l^nl
基本算法与求 n 的因数办法一样，但每次用来除以 n 的质因数 P₁ 必须一直重复除 n ，直至 n MOD i <> 0 为止，则此时的质因数 P₁ 就完全从 n 中分解出来了。
程序清单：
Qbasic
CLS
INPUT n
DIM a(n)
m = n
FOR i = 2 TO n - 1
k = 1
DO WHILE k <> 0
   r = m MOD i
   IF r = 0 THEN
     t = t + 1
     a(t) = i
     m = m \ i
     'PRINT a(t);
   ELSE
     k = 0
   END IF
LOOP
NEXT
PRINT n; "=";
IF t = 0 THEN
PRINT " 1 *"; n
ELSE
FOR i = 1 TO t
    IF i = 1 THEN
      PRINT a(i);
    ELSE
      PRINT "*"; a(i);
    END IF
NEXT
END IF
END

作者：
来源：淮安市信息技术教学教研网
时间：2002-01-25

上一篇：ASCⅡ码字符串输出
下一篇：Jsoi信息学奥林匹克友谊赛