核心思路:
本题题意为给定一个数字去寻找它的最长的连续的因子,如果一样长的话就输出数字比较小的那一组
样例中给定630可以分解为3 * 5 * 6 * 7,其中的3是迷惑人的,求出5 6 7为最长连续因子
然后对于一个数字可能是素数那么就是输出1然后换行再输出它本身
也可能是合数那我们就从2开始判断一直判断到它的根号大小,以哪一个数字为开头时可以获得最长连续因子
我们用一个vector存储答案,第二个vector存储现在这次处理的结果,如果这次的长度比现存答案的长那么就进行替换
如果一个数字一旦可以整除后就放入vector中,并且被除数也随之改变,一旦不可以整除就进行两个vector长度的比较
当判断完每一个数字开头对应的最长连续因子后,输出存储的答案即可。
C++ 代码
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector<int>v1;
vector<int>v2;
int main() {
int x;
scanf("%d",&x);
bool st=1;
int t=x;
for (int i = 2; i <= sqrt(x)+1; ++i) {
for (int j = i; j <=sqrt(x)+1 ; ++j) {
if (t%j==0)
{
t/=j;
if (st==1)
{
v1.push_back(j);
}
else{
v2.push_back(j);
}
}
else{
//代表遇到不能整除的了就得打断
if (!v1.empty())
st=0;
if (v2.size()>v1.size())
{
v1=v2;
}
v2.clear();
t=x;
break;
}
}
}
if (v1.empty())
{
cout<<"1"<<endl;
cout<<x<<endl;
return 0;
}
cout<<v1.size()<<endl;
for (int i = 0; i < v1.size(); ++i) {
if (i==0)
cout<<v1[i];
else cout<<"*"<<v1[i];
}
}
为什么要sqrtx(x)+1啊佬
哈哈哈当时好像也没仔细考虑,就感觉范围大一点别少了就行