【洛谷】P1075 [NOIP2012 普及组] 质因数分解(详解)

发布于:2024-12-07 ⋅ 阅读:(114) ⋅ 点赞:(0)

#include <iostream>
#include <cmath>
using namespace std;
//函数声明,声明一个名为isP的函数该函数接受一个整型参数x,用于判断x是否为质数
bool isP(int x); 

int main()
{
//定义一个整型变量 n,用于接收从标准输入读取的整数,此整数按照题目要求是两个不同质数的乘积
    int n; 
    cin >> n;
//定义整型变量t并初始化为1,t用于存储最终要输出的较大的质数因数,初始值1当作在未找到时的默认值
    int t = 1; 
//开启一个for循环,循环变量i从2开始,每次递增1,直到i不超过输入整数 n 的平方根(包含平方根)
//这是因为如果n是两个不同质数的乘积,那么较小的那个质数必然小于等于sqrt(n)
    for (int i = 2; i <= sqrt(n); i++) 
    {
        //调用isP函数来判断当前的数字i是否为质数,函数返回值为true,即i是质数
        if (isP(i)) 
        {
            //当i是质数时,进一步判断n是否能被i整除,也就是判断i是否为n的因数
            if (n % i == 0) 
            {
     //如果i既能整除n,那么通过n除以i得到另一个因数(也就是两个不同质数因数中较大的那个)
                t = n / i; 
                //一旦找到符合条件的较大质数因数,就无需再继续循环查找了,直接跳出循环
                break; 
            }
        }
    }
    //将最终确定的两个不同质数因数中较大的那个质数(存储在变量 t 中)输出到控制台
    cout << t; 
    return 0;
}

//定义 isP 函数,用于判断传入的整数 x 是否为质数
bool isP(int x)
{
    int i;
    //通过一个for循环,循环变量i从2开始,每次递增1,直到i不超过 x 的平方根(包含平方根)
    //原理是如果一个数存在大于其平方根的因数,必然也存在小于其平方根的对应因数
    for (i = 2; i <= sqrt(x); i++) 
    {
        //在循环过程中,如果发现 x 能被 i 整除,说明 x 不是质数,直接跳出循环
        if (x % i == 0) 
            break;
    }
    //当循环结束后,如果i的值大于x的平方根,意味着在整个循环过程中
      除了1和x本身外,没有找到能整除x的数,所以x就是质数,此时函数返回true(用 1 表示)
    if (i > sqrt(x)) 
        return 1;
    else
    //若i的值不大于x的平方根,说明在循环过程中
      找到了能整除x的其他数,那么 x 不是质数,函数返回 false(用 0 表示)
        return 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到