引用

可以看看这位大佬的证明，个人感觉挺详细的，但是没看明白hhh。自始至终对数学都慢半拍

haust_fx 1.试除法判定质数 2.分解质因数 质数

题目描述

This problem is a programming version of Problem 3 from projecteuler.net

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

What is the largest prime factor of a given number N ?

样例

Input Format

First line contains T, the number of test cases. This is followed by T lines each containing an integer N.

Output Format

For each test case, display the largest prime factor of N.

Constraints

1≤1 \leq T ≤10\leq 10
10≤10 \leq N ≤1012\leq 10^{12}

Sample Input 0

2
10
17

Sample Output 0

5
17

Explanation 0

Prime factors of 10 are {2,5}, largest is 5.
Prime factor of 17 is 17 itself, hence largest is 17.

算法

(数论) O(1)O(1)

对于试除法分解质因数的证明我就不解释了，我也不是很明白2333。感兴趣的可以看看这个1.试除法判定质数 2.分解质因数 质数。这位大佬有给出具体证明，还是挺详细的。

要找到质因数首先我们得先找到因数，然后看看这个因数是不是质数，再和上一个质因数比较或者存入数组中。这是我想到的朴素做法。

但是试除法分解质因数不需要这么做，他能快速找出所有质因子。

时间复杂度 O(n)O(\sqrt{n})

C++ 代码

#include <iostream>

using namespace std;

typedef long long LL;

int n;

int main()
{
    cin >> n;
        
    while (n --)
    {
        LL t , res = 0;
        
        cin >> t;
        // 一个数的因子是成对存在的，那么比较小的那一个必定不会超过根号n
        for(LL i = 2; i <= t / i; i ++)
        {
            if(t % i == 0)
            {
                while(t % i == 0) t /= i;
                // 每一次的质因子都比前一个大，所以直接更新
                res = i;
            } 
        }
        // 因为可能刚好这个数本来就是质数，那么它的最大质因子就是他自己，如果这个数有因子的话，最后必定会为1
        if(t > 1) res = max(res , t) , cout << res << endl;
        else cout << res << endl;
    }
    
    return 0;
}