题解 | #质数因子#

#include <stdio.h>
#include <math.h>
#include <limits.h>

int isPrime(int num);
int FindLeastPrime(int min, int num);
void showAllPrimeFactor(void);

int main() {
    int a, b;
    #if 0
    while (scanf("%d %d", &a, &b) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to 
        printf("%d\n", a + b);
    }
    #endif
    //printf("INT_MAX=%lld",INT_MAX);//=2147483647~2*10^9 20亿
    showAllPrimeFactor();
    return 0;
}

//一些可能的输入和输出
//1-----> 没有
//2-----> 2
//3---->3
//4-----> 2 2
//18 2 3 3
//200 2 2 2 5 5
//常见的质数：2, 3 ,5, 7, 11
void showAllPrimeFactor(void)
{
    int InputNum = 0;
    int testNum = 2;
    scanf("%d", &InputNum);
    #if 0
    if((InputNum<1)||(InputNum > 2*pow(10,9)+14))
    {
        printf("input error!\n");
        return;
    }
    #endif
    while(InputNum!=1)
    {
        //1.准备一个数n，用于判定这个数是不是质数。这个数不断增大。
        //2-1.如果n是质数，用InputNum%n，如果结果是0，表明n是质因数
        //打印出这个n，循环。直到InputNum%n!=0
        
        if(isPrime(InputNum))
        {
            printf("%d ",InputNum);
            InputNum = 1;
        }
        else if(isPrime(testNum) && (InputNum%testNum==0))
        {
            do
            {
                InputNum /= testNum;
                printf("%d", testNum);
                printf(" ");
            }while(InputNum%testNum==0);
        }
        else //3.如果n不是质因数，让n增加
        {
            testNum++;
        }
    }
}

/*
*@功能：判断一个数是不是质数
*@返回值：0--不是质数 1--是质数
*/
int isPrime(int num)
{
    if(num==1)
    {
        return 0;
    }
    for(int i=2; i<=(int)sqrt(num); i++)
    {
        if((num%i)==0) return 0;
    }
    return 1;
}