题目描述
已知正整数 n 是两个不同的质数的乘积, 试求出较大的那个质数.
输入描述:
输入只有一行, 包含一个正整数 n.
输出描述:
输出只有一行, 包含一个正整数 p, 即较大的那个质数.
示例 1
输入
复制
21
输出
复制
7
备注:
对于 60% 的数据, 6≤n≤1000.
对于 100% 的数据, 6≤n≤2*10^9.
解析:
说实话, 看到这个题目是不是就觉得得分别判断这两歌树是不是质数. 一开始我就想先暴力找到一个能被 n 整除的较小的质数, 然后用 n/min 不就行了吗, 可是后来一想, 不对呀, 不能保证大的数也是质数呀, 于是, 我就看了看数据, 还是硬着头皮将这个想法敲上了, 一提交竟然对了??? 黑人问号??? 可是后来一想, 给出的这个数肯定能分解成两个质因数, 而像 24,100 这样的数, 肯定就不在考虑范围了.
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string>
- #include <cstring>
- #include <cstdlib>
- #include <cmath>
- #include <stack>
- #include <queue>
- #include <set>
- #include <map>
- #include <vector>
- #include <ctime>
- #include <cctype>
- #include <bitset>
- #include <utility>
- #include <sstream>
- #include <complex>
- #include <iomanip>
- #define inf 0x3f3f3f3f
- typedef long long ll;
- using namespace std;
- ll n;
- int main()
- {
- cin>>n;
- for(int i=2; i<=n/2; i++)
- {
- if(n%i==0)
- {
- cout<<n/i<<endl;
- break;
- }
- }
- return 0;
- }
质因数分解
来源: http://www.bubuko.com/infodetail-3319453.html