[NOIP2012 普及组] 质因数分解

[NOIP2012 普及组] 质因数分解

题目描述

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

输入格式

输入一个正整数 n。

输出格式

输出一个正整数 p，即较大的那个质数。

样例 #1

样例输入 #1

21

样例输出 #1

7

首先需要写一个函数是否是素数

bool isP(int num)
{
    bool flag = true;
    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            flag = false;
            break;
        }
    }
    return flag;
}

然后我们只需要遍历小于的整数，看其是否是n的素因数

注意：当我们遍历小于的整数时，也对应遍历了大于小于n的整数

完整代码如下

#include<iostream>
#include<cmath>
using namespace std;
bool isP(int num)
{
    bool flag = true;
    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            flag = false;
            break;
        }
    }
    return flag;
}
int main()
{
    int n;
    cin >> n;
    int max = 1;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0 && isP(i))
        {
            max = max > i ? max : i;
            if (isP(n / i))
            {
                max = max > n / i ? max : n / i;
            }
        }
    }
    cout << max;
    return 0;
}