Project_Euler-03 题解

题目

思路

首先排除掉暴力求解，虽然也可以得出答案，但是我在我仅仅只有二颗核心的服务器上跑了很久很久…

尝试另一种方法：

首先要知道一个知识，所有的数都可以拆解成为素数因子平方连乘的形式：

以12为例子：

$$\begin{gathered} 12=3\ast 4 \\ 12=3^1\ast 2^2 \end{gathered}$$

2和3都是素数。

以168为例子：

$$\begin{gathered} 168=7\ast 8\ast 3 \\ 168=7^1\ast 2^3\ast 3^1 \end{gathered}$$

2，3，7都是素数。

因此，我们可以从小到大枚举所有素数，在枚举的过程中，将这些素数记录下来，保留最大的一个，同时剔除目标数中的这些素因数，直到枚举的素数大于目标数为止。

另外还需要知道：

• 当一个数不是质数时，必定存在两个约数，一个大于等于sqrt(n)，另一个小于sqrt(n)
• 埃式筛思想

程序

具体实现请看注释：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<time.h>
#define N 600851475143LL
#define ll long long

int main(){
	// i 表示要枚举的素因子，ans是最终的结果，num是目标数
    ll i = 2, ans = 0, num = N;
    // 循环条件利用了一个性质，一个数的其一个因子不会大于该数的根值
    while (i * i <= num){
    	// 如果目标数可以整除当前枚举的因数，那么将其记录下来
        if(num % i == 0) ans = i;
        // 然后剔除该因数
        while (num % i == 0) num /= i;
        // 不用担心枚举到非素数，因为非素数也是由素数组成的，在之前剔除素数时，也相当于剔除了非素数。
        // 例如，4，因为2被剔除了，所以2的倍数更不可能存在，这也是埃式筛的思想。
        i += 1;
    }
    // 在剔除过程中，有可能直接将目标数剔除为1，这说明最后一个被枚举的因子就是最大质因数，
    // 但是如果不是1说明剩下的一部分是最大质因数，这里利用了题解最后列出思想的第一点
    if (num != 1) ans = num;
    printf("%lld\n", ans);
    return 0;
}