C趣味程序(二)(08)

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:44:32

2.2.1 分解质因数乘积形式
2.2.2 分解质因数指数形式



2.2 分解质因数
2.2.1 分解质因数乘积形式
    把指定区间上的所有整数分解质因数，每一整数表示为质因数从小到大顺序排列的乘积形式。假如被分解的数本身是素数，则予以注明。
    例如，90=2*3*3*5，91=素数。
算法分析如下：
    对每一个被分解的整数i，赋值给b(以保持判别运算过程中i不变)，用k(从2开始递增1取值)试商：
        若不能整除，说明该数k不是b的因数,k增1后继续试商。若能整除，说明该数k是b的因数，打印出"*k"，b除以k的商赋给b(b=b/k)后继续用k试商(注重，可能有多个k因数)，直至不能整除，k增1继续。
    按上述从小到大试商确定的因数显然为质因数。
    循环取值k的终值如何时确定，一定程度上决定了程序的效率。终值定为i-1或i/2，试商循环次数都比较大，无效循环太多。循环终值定为i的平方根sqrt(i)可大精简试商次数，此时对于大于sqrt(i)的因数(至多1个!)，在试商循环结束后要注重补上，不要遗失。
    假如整个试商后b的值没有任何缩减，仍为原来的待分解数i，说明i是素数，作素数说明标记。
程序代码如下：
程序运行结果如下：
#include<stdio.h>
#include<math.h>
void main()
{
    long int b,i,k,m,n,w=0;
    printf("[m,n]中整数分解质因数.\n");
    printf("请输入m,n:");
    scanf("%ld,%ld",&m,&n);
    for(i=m;i<=n;i++)            /*i为待分解的整数*/
    {
        printf("%ld=",i);
        b=i;k=2;
        while(k<=sqrt(i))        /*k为试商因数*/
        {
            if(b%k==0)
            {
                b=b/k;
                if(b>1){printf("%ld*",k);continue;}    /*k为质因数，返回再试*/
                if(b==1) printf("%ld\n",k);
            }
                k++;
            }
            if(b>1&&b<i) printf("%ld\n",b);        /*输出大于i平方根的因数*/
            if(b==i){printf("(素数!)\n");w++;}      /* b=i,表示i无质因数*/
        }
        printf("其中共%d个素数.\n",w);
 
}
程序运行结果如下：

------------------------------------------------------------

2.2.2 分解质因数指数形式
    对；输入的整数分解质因数，假如有相同的素因子要求写成指数形式，例如分解1960，写成1960=2³*5*7²
算法分析如下：
    在以上程序的基础上，需作一些变通：引入变量j统计素因子的个数，j=1时不打印指数,j>1时需加印指数(^j)。这样程序须设置相应指数的判别操作。
程序代码如下：
程序运行结果如下：
#include<stdio.h>
#include<math.h>
void main()
{
    long int b,i,j,k,m,n,w=0;
    printf("m--n中整数分解.\n");
    printf("请输入m,n:");
    scanf("%ld,%ld",&m,&n);
    for(i=m;i<=n;i++)
    {
        printf("%ld= ",i);
        b=i;k=2;j=0;
        while(k<=sqrt(i))
        {
            if(b%k==0)
            {
                b=b/k;j++;continue;}
                if(j>=1)
                {
                    printf("%ld",k);
                    if(j>1)printf("^%ld",j);
                    if(b>1)printf("*");
                }
                k++;j=0;
            }
            if(b>1&&b<i) printf("%ld",b);
            if(b==i){printf("(素数!)"); w++;}
            printf("\n");
        }
        printf("其中共%ld个素数.\n",w);
}
程序运行结果如下：

上一篇：{实例}C趣味程序(二)(07) 人气:6863
下一篇：{实例}C趣味程序(二)(09) 人气:6155

C语言程序设计视频教程