GESP5级T1真题 [202309] 因数分解——O(sqrt(n))的时间复杂度，值得一看

描述

每个正整数都可以分解成素数的乘积，例如：6=2*3、20=22 *5
现在，给定一个正整数N，请按要求输出它的因数分解式。

输入描述

输入第一行，包含一个正整数N。约定2<=N<=10^12

输出描述

输出一行，为N的因数分解式。要求按质因数由小到大排列，乘号用星号*表示，且左右各空一格。当且仅当一个素数出现多次时，将它们合并为指数形式，用上箭头^表示，且左右不空格。

用例输入 1 

6

用例输出 1 

2 * 3

用例输入 2 

20

用例输出 2 

2^2 * 5

用例输入 3 

23

用例输出 3 

23

来源

GESP 五级

这道题就算用O(n)的方法也过不了，所以要用O(sqrt(n))，这道题的关键就是在这里。

众所周知，i*i<=n就是sqrt(n)的时间复杂度，那我们就要在其基础上写代码

ACcode

#include <bits/stdc++.h>
using namespace std;long long n;
bool flag=false,f2;
int main() {cin>>n;for (int i=2;i*i<=n;i++){if (n%i==0){f2=1;int cnt=0;while (n%i==0) n/=i, cnt++;//O(sqrt(n))+O(log2n)=O(sqrt(n))if (flag==false){flag=true;}else cout<<" * ";if (cnt>1){cout<<i<<"^"<<cnt;}else cout<<i;}}if(f2==0){cout<<n;}else if(n!=1)cout<<" * "<<n;return 0;
}

感谢王大佬提供思路

 看了这么久，作者也写了这么久，能不能点一个赞，在收藏一下呢？最好的话在点个关注吧

谢谢啦！