分解质因数

问题：2805 = 17*11*5*3

 

int main(void)
{
    int a, n=100;
    printf("pls input the number:\n");
    scanf("%d", &n);
    for(a = 2; a < n; ++a)
    {
        if(n%a == 0)
        {
            n /= a;
            printf("%d * ", a);
            a = 1;
        }
    }
    printf("%d\n", a);

    return 0;
}

 

====================================

 

算法：i从2开始到sqrt(n)的每一个i去试除n，
      能整除的时候就说明找到了一个新的因子，
      因为是从较小的数开始除起所以必定会先找到能整除的最小的素数。

参考：blog.csdn.net/xinghongduo/article/details/5809607

      blog.csdn.net/cherylnatsu/article/details/6423465

#include <stdio.h>

// n从2开始
void primfactor(long m, int n)
{
    while(m%n!=0) n++; // 能整除
    m /= n;
    if(m>=n)
        primfactor(m,n);
    printf("%d*",n);
}

//非递归算法
void primediv(int num )
{
    int i;
    // i<= sqrt(num)
    for(i=2; i*i <= num; ++i)
    {
        if(num%i == 0)
        {
            num /= i;
            printf("%d*", i);
            --i; // same factor
        }
    }
    printf("%d\n", i);
}

main()
{
// 435234=251*17*17*3*2
// 300=5*5*3*2*2
    long n=435234;
    printf("%ld=",n);
    primfactor(n,2);
    printf("\n");
    // another
    printf("%ld=",n);
    primediv(n);
}