题解 | #质数因子#

此题通过从2开始去找数n的质因数，用例输入2000000014过不了，因为2000000014的质因数为2和1000000007,后面是一个非常大的素数，在for循环中就相当于直接遍历1000000007了，会超时。通过引入判断是否为素数来进行优化。素数的判断也是经过了优化的，参考我的另一篇文章《利用孪生素数判断是否为素数》，地址：https://blog.nowcoder.net/n/52c9640ea14a4330a842e783429698b5

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

using namespace std;

bool is_prime(long n)
{
    if(n==2 || n==3) return false;
    if(n%6!=1 && n%6!=5) return false;

    //到这里，留下来的n只可能是6N+1或者6N+5;
    long div = 5;
    long t = n/div;
    while(t>=div)
    {
        //n可能是(6N+1)与(6N+5)两个因子的乘积，故需要在这里进行判断;
        if(n%div==0 || n%(div+2)==0) return false;
        div += 6;
        t = n/div;
    }
    return true;
}

void fun(long n)
{
    for(long i=2;i<=n;i++)
    {
        //用例输入2000000014过不了，这里通过判断是否为素数来提前结束;
        if(is_prime(n))
        {
            printf("%ld",n);
            return;
        }

        while(n % i == 0)
        {
            printf("%d ",i);
            n /= i;


        }
    }
}

int main()
{
    long n;
    while(scanf("%ld",&n) != EOF)
    {
        fun(n);
    }
    return 0;
}