GESP二级 - 质因数分解

题目描述

已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。

输入描述

输入只有一行，包含一个正整数 n。

• 对于60%的数据，6≤n≤1000。
• 对于100%的数据，6≤n≤2×10^9。

输出描述

输出只有一行，包含一个正整数 p，即较大的那个质数。

用例输入 1

21

用例输出 1

7

C++ 代码实现

#include <iostream>
using namespace std;

// 判断一个数是否为质数
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;

    // 从n的平方根开始往下找第一个质数
    for (int i = n / 2; i >= 2; i--) {
        if (n % i == 0 && isPrime(i)) {
            cout << i << endl;
            break;
        }
    }

    return 0;
}

代码解析

1. isPrime函数: 用于判断一个数是否为质数。从2开始遍历到该数的平方根，如果该数能被遍历到的任何数整除，则该数不是质数，否则为质数。
2. 主函数: 首先读取输入的整数n，然后从n的平方根开始往下遍历，如果遍历到的数能整除n，且该数为质数，则输出该数并结束循环。

优化建议

1. 由于n是两个不同质数的乘积，因此较大的质数一定是n的因子，可以先遍历n的所有因子，再判断该因子是否为质数，这样可以减少循环次数，提高效率。
2. 在isPrime函数中，可以使用更优化的质数判断方法，例如使用埃氏筛法或Miller-Rabin测试。

总结

本文详细讲解了GESP二级编程题 - 质因数分解的解题思路，并提供C++代码实现。文章还包括代码优化建议和样例测试用例。希望对读者理解和解决此类问题有所帮助。