C语言算法之19：分解质因数

XYD漫漫

C语言算法之19：分解质因数 [复制链接]

手一定要越过思想的额头，行动高于一切。

 

学技术，重在日拱一卒、一点一滴的积累。

 

今天一起分析C语言的算法之19：分解质因数。

 

算法题目：将一个正整数分解质因数。

 

例如：输入90,打印出90=2*3*3*5。

 

说明：图片来自网络

 

 

编程思路分析

 

质因数（素因数或质因子）：

 

在数论里是指能整除给定正整数的质数。

 

除了1以外，两个没有其他共同质因子的正整数称为互质。

 

因为1没有质因子，1与任何正整数（包括1本身）都是互质。

正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式 。

 

只有一个质因子的正整数为质数。

 

每个合数都可以写成几个质数（也可称为素数）相乘的形式 ，这几个质数就都叫做这个合数的质因数。

 

如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。

 

编程思路：用for语句和if语句嵌套实现。

 

程序范例

 

#include<stdio.h>

 

void number(int n);

 

int main()

{

    int n;

    printf("请输入一个整数：");

    scanf("%d",&n);

    number(n);

    return 0;

}

 

void number(int n)

{

    int temp=n;

    int i,j=0；

    int a[20]={0};

 

    for(i=2;i<=n;i++)

    {

        if(n%i==0)

        {

            a[j++]=i;

            n=n/i; //去掉这一部分

            i=1; //重新从1开始判断

        }

    }

    printf("%d=%d",temp,a[0]);

    for(i=1;i<j;i++)

    {

        printf("*%d",a);

    }

    printf("\n");

}

 

程序运行结果案例：

Verifone

看起来不错，不知道效率怎么样，似乎效率不是很高

Gen_X

思路很好，学习了！