C语言程序设计100例之（5）：分解质因数

例5    分解质因数

题目描述

将一个正整数分解质因数。例如：输入90，输出 90=2*3*3*5。

输入

输入数据包含多行，每行是一个正整数n (1<n <100000) 。

输出

对于每个整数n将其分解质因数。

输入样例

90

256

199

输出样例

90=2*3*3*5

256=2*2*2*2*2*2*2*2

199=199

        （1）编程思路。

对整数n进行分解质因数，应让变量i等于最小的质数2，然后按下述步骤完成：

1）如果i恰等于n，则说明分解质因数的过程已经结束，输出即可。

2）如果n<>i，但n能被i整除，则应输出i的值，并用n除以i的商，作为新的正整数n，转第1）步。

3）如果n不能被i整除，则用i+1作为新的i值，转第1）步。

因此，程序主体是一个循环，在循环中根据n能否整除i，进行两种不同处理，描述为：

        i=2;

       while(i<n)

       {

            if(n%i==0)

            {

                       printf("%d*",i)     // i是n的因数，输出i

                       n=n/i;            // 对除以因数后的商在进行分解

            }

           else

                  i++;             // 找下一个因数

      }

        （2）源程序。

#include <stdio.h>

int main()

{

   int n,i;

   while (scanf("%d",&n)!=eof)

   {

        printf("%d=",n);

        i=2;

        while(i<n)

        {

            if(n%i==0)

            {

                printf("%d*",i);

                n=n/i;

           }

           else

                i++;

        }

        printf("%d\n",n);

   }

   return 0;

}

习题5

5-1  完全数

题目描述

完全数（perfect number）又称完美数或完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和，恰好等于它本身。

例如：第一个完全数是6，它有约数1、2、3、6，除去它本身6外，其余3个数相加，1+2+3=6。第二个完全数是28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。

编写一个程序，求两个正整数之间完全数的个数。

输入

输入数据包含多行，第一行是一个正整数n，表示测试实例的个数，然后就是n个测试实例，每个实例占一行，由两个正整数num1和num2组成,(1<num1,num2<10000) 。

输出

对于每组测试数据，请输出num1和num2之间（包括num1和num2）存在的完全数个数。

输入样例

2

2 5

5 7

输出样例

0

1

         （1）编程思路。

        要求num1和num2之间的所有完全数，需要对num1~num2范围内的每一个数n，计算n的所有真因子之和s，若n==s，则n就是一个完全数。框架描述为：

         for(n=num1;n<=num2;n++)

         {

                   计算n的真因子之和s ；

                   if(s==n)

                            是完全数，计数；

         }

        为计算n的所有真因子之和s，可令s初值为1（1是n的真因子），然后用2~n-1范围内的每个i去除n，如果n能被i整除（即n%i==0），则i是n的真因子，s=s+i。

        实际上，i（i>1）是n的真因子，则n/i也是n的真因子。因此，可以将i的范围缩小为2~sqrt(n)。这样，计算n的真因子之和s的操作描述为：

                   s=1;                                                // s为n的真因子之和

                   for(i=2;i<=sqrt(n);i++)                // 求解真因子之和

                            if(n%i==0)

                                     if (i!=n/i)  s=s+i+n/i;

                else  s=s+i;

        因此，程序可以写成一个嵌套的二重循环。

       （2）源程序。

#include <stdio.h>

#include <math.h>

int main()

{

         int t,num1,num2,i,n,s,cnt;

         scanf("%d",&t);

        while (t--)

        {

            scanf("%d%d",&num1,&num2);

            cnt=0;

            if (num1>num2) { n=num1; num1=num2; num2=n;}

             for(n=num1;n<=num2;n++)

             {

                       s=1;                                                // s为n的真因子之和

                       for(i=2;i<=sqrt(n);i++)                // 求解真因子之和

                               if(n%i==0)

                                {

                                         if (i!=n/i)  s=s+i+n/i;

                                         else  s=s+i;

                                 }

                       if(s==n)  cnt++;

            }

            printf("%d\n",cnt);

      }

      return 0;

}

5-2  亲和数

题目描述

遥远的古代，人们发现某些自然数之间有特殊的关系：如果两个数a和b（a不等于b），a的所有真因数之和等于b，b的所有真因数之和等于a，则称a、b是一对亲和数。

例如220和284，1184和1210，2620和2924，5020和5564，6232和6368。

给定一个正整数 s（6≤s≤18000） ，找出a，b两数中至少有一个不小于s的第一对“亲和数” 。

输入格式

一行一个整数s。

输出格式

一行两个整数a 和 b（用空格隔开）。a 表示第一个不小于 s 的有“亲和数”的整数，b是a的“亲和数”。

输入样例 #1

206

输出样例 #1

220  284

输入样例 #2

260

输出样例 #2

284  220

        （1）编程思路。

        程序对输入整数begin开始的自然数进行穷举，算法描述为：

         for(n=begin；；n++)

         {

                   计算n的真因子之和 s ；

                   if （s==n） continue；

                   计算s的真因子之和 m ；

                   if(m==n)                        // 如果两数相等，是解

                   {

                          输出解的情况；

                   }

         }

        计算自然数的真因子之和的方法，可以参见前面的习题5-1“完全数”。

       （2）源程序。

#include <stdio.h>

#include <math.h>

int main()

{

         int begin,i,n,s,m,k;

         scanf("%d",&begin);

         for(n=begin;;n++)

         {

                   s=1;                                                   // s为n的真因子之和

                   k=1;                                                  // k为n的真因子个数

                   for(i=2;i<=(int)sqrt(1.0*n);i++)          // 求解真因子之和

                            if(n%i==0)

                            {

                                     s=s+i+n/i;

                                     k+=2;

                            }

                  i--;

                  if (i*i==n) s-=i;

                  if(k==1 || s==n)                                    // 若n为质数或完数，进行下次循环

                            continue;

                   m=1;                                                   // m为s的真因子之和

                   for(i=2;i<=(int)sqrt(1.0*s);i++)

                            if(s%i==0)

                                     m+=i+s/i;                       // 计算s的真因子之和

                   i--;

                   if (i*i==s)  m-=i;

                   if(m==n)                                      // 如果两数相等，输出亲和数

                   {

                            printf("%d %d\n",n,s);

                            break;

                   }

       }

       return 0;

}

5-3  the number of divisors about humble numbers

problem description

a number whose only prime factors are 2,3,5 or 7 is called a humble number. the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.

now given a humble number, please write a program to calculate the number of divisors about this humble number.for examle, 4 is a humble,and it have 3 divisors(1,2,4);12 have 6 divisors.

input

the input consists of multiple test cases. each test case consists of one humble number n,and n is in the range of 64-bits signed integer. input is terminated by a value of zero for n.

output

for each test case, output its divisor number, one line per case.

sample input

4

12

0

sample output

3

6

       （1）编程思路。

        若一个大于1正整数n可以分解质因数：n=(p1^a1)*(p2^a2)*(p3^a3)*…*(pk^ak),

        则由约数个数定理可知n的正约数有 (a1+1)(a2+1)(a3+1)…(ak+1)个。

        本题要求一个给定丑数n的约数个数，而一个丑数分解质因数后，其质因子只有2、3、5或7这4个，因此只需求出n中分别含有质因子2、3、5和7的个数即可。

        （2）源程序。

#include <stdio.h>

int fun(__int64 n,int x)    // 求整数n分解质因数后含质因子x的个数

{        int sum=0;

         while(n%x==0)

         {

                   sum++;

                   n/=x;

         }

         return sum;

}

int main()

{

         int cnt1,cnt2,cnt3,cnt4;

         __int64 n;

         while(scanf("%i64d",&n) && n!=0)

         {

                   cnt1=cnt2=cnt3=cnt4=1;

                   cnt1+=fun(n,2);

                   cnt2+=fun(n,3);

                   cnt3+=fun(n,5);

                   cnt4+=fun(n,7);

                   printf("%d\n",cnt1*cnt2*cnt3*cnt4);

         }

         return 0;

}