TB椰程 TypeBuddy 打字搭子

质因数分解

洛谷·深入浅出 · 代码 · cpp · 难度 3/5 · 共 379 字

n 为两不同质数积，输出较大质数

  • 洛谷
  • 练习

正文

// 原题：https://oj.yecheng.tv/p/1389
// 题意：已知 n 是两个不同质数的乘积，求较大的那个质数。
// 思路：从 2 起找最小质因数 i，则较大质数为 n/i。
// 复杂度：O(sqrt(n))。
// 易错点：只需找到最小质因数即可；n/i 即为较大者。
#include <iostream>
using namespace std;
int main(){
    long long n;
    cin >> n;
    for(long long i = 2; i * i <= n; i++){
        if(n % i == 0){ cout << n / i << endl; return 0; }
    }
    cout << n << endl;
    return 0;
}

洛谷·深入浅出的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK