质因数分解

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 515 字

已知正整数n是两个不同质数的乘积，输出其中较

一本通
练习

正文

/*
原题：T1620「一本通 6.2 练习 1」质因数分解（NOIP 2012 普及组）
题意：已知正整数 n 是两个不同质数的乘积，输出其中较大的那个质数。
思路：从 2 试除到 √n，第一个整除 n 的 i 必为较小质因子，较大质因子即为 n/i。
复杂度：时间 O(√n)，空间 O(1)
易错点：1) n 可达 2e9，用 long long 且 i*i 勿溢出；2) 题目保证有两个不同质因子，首个因子即较小者。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin>>n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            cout<<n/i<<"\n";
            return 0;
        }
    }
    cout<<n<<"\n";
    return 0;
}

质因数分解

正文

一本通·提高篇的其它内容