3.Largest prime factor

问题描述

The prime factors of $13195$ are $5$,$7$,$13$ and $29$.

What is the largest prime factor of the number $600851475143$?

解法

1. 题意是找到$600851475143$的最大质因子

   例如 ：45可以分解成

   $$45 = 3 * 3 * 5$$

   它的质因子就是3，5 即45的最大质因子就是5

   我们可以将其表示为该过程:

   • 遍历自然数(从$2$开始)，若$n$能够被$k$整除，则重复整除它，直到不能除尽为止。

     然后再用$k + 1$ 重复上述操作

   例如：$45$除以$2$整除不了 则$45$ 除以$3$ 得到$15$ $15$ 再除以$3$得到$5$，$5$除以$4$无法整除，则$5$除以$5$得到$1$ 则循环结束。

#include <bits/stdc++.h>
#define ll long long
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
using namespace std;
//！long long表示 int会溢出
const ll ans = 600851475143;
void solve(ll n)
{
    ll factor = 2;//从2开始除嘛~
    while(n > 1)
    {
        if(n % factor == 0)
        {
            printf("%d ", factor);//选取最后一个即可
            n /= factor;
        }
        factor++;
        //此处可以优化为:factor += (factor == 2 ? 1 : 2)
        //因为素数除了2之外都是奇数
        //也就是从2 -> 3 时加1 其余时候都加2
        //补充:当factor的平方大于n时，必定只有n这一个因子。
    }
}
int main(void)
{
    IOS
    solve(ans);
    return 0;
}

1. 数学解法：

   我们可以考虑一个定理：

   算数基本定理：

   $$任何一个大于1的自然数N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积\\ 即：N = P_1 * P_2 *P_3 ......*P_n (其中P_1 < P_2<P_3 ......<P_n)$$

   根据题意我们可以知道我们要计算的就是$P_n$

   我们首先找到 对于N来说的一个最小质数因子 即$P_1$，然后我们再对于$N$来说，去除$P_1$,依次往下。最后当$P_x = P_n$时，得到的$P_x$ 就是最大的质因子。

#define ll long long
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
using namespace std;
//1e8 不能采用素数筛
const ll ANS = 600851475143;
ll isprime(ll x)
{
    for(ll i = 2; ; i++)
    {
        if(x % i == 0)
            return i;
    }
}
int main(void)
{
    IOS
    ll prime_number = ANS;
    ll min_prime_number = isprime(prime_number);
    while(min_prime_number != prime_number)
    {
        prime_number /= min_prime_number;
        min_prime_number = isprime(prime_number);
    }
    cout << prime_number << endl;
    return 0;
}

注意点

1. 不可以采用素数筛 会超时。
2. 以下代码从3开始 某种程度来说 不够严谨 但求的时$P_n$故可得到正确结果。

​```C++

include

define ll long long

define IOS {ios::sync_with_stdio(false);cin.tie(0);}

using namespace std;

//1e8 不能采用素数筛
const ll ANS = 600851475143;
ll isprime(ll x)
{
for(ll i = 3; ; i += 2)
{
if(x % i == 0)
return i;
}
}
int main(void)
{
IOS
ll prime_number = ANS;
ll min_prime_number = isprime(prime_number);
while(min_prime_number != prime_number)
{
prime_number /= min_prime_number;
min_prime_number = isprime(prime_number);
}
cout << prime_number << endl;
return 0;
}

```

正确答案

$$Answer:6857$$

官方解答