分析：本题目有两个要点，一是如何将字符串中的数字提取出来并计算成对应的整数
而是求出这个数的最大质因子
需要注意的是：1.质数的最大质因子就是其本身，一个合数总可以分解为几个质因子之积，所以并无需验证是否为质数
2.一个合数如果有超过根号n的质因子，有且仅有一个，
/*对于本题而言，下边使用了快速分解定理：1、即对于一个合数总存在有质数因子，所以我们在分解合数的时候不需要判断被整除的因子是否为质数。2、理解是一个难点，对于一个合数，我们将小于等于这个合数平方根的质因子整除完之后，若余下的书大于1，说明本合数存在并且仅存在一个大于这个合数的平方根的质因子*/#include<iostream>#include<vector>#include<string>#include<math.h>using namespace std;const int maxn = 100000;int max_yinzi(int n){ int max =0; for(int i=2;i<=sqrt(1.0*n);i++)//从2到根号n求其质因数 { while(n%i==0) //因为一个质因数可能会乘多次，所以应该用while，而不是if { max = i; //让max指向当前最大值 n /= i; //除以质因数 } if(n==1) break; } if(n!=1) //如果n不等于1，说明存在一个大于根号n的质因数，有且仅有一个，即等于当前的n max = n; return max;}int main(){ int n; vector<string> str; char ch[101]; string temp; int sum; double count; while(cin>>n) { str.clear();//清空 getchar(); //用在gets()之前 for(int i=0;i<n;i++) { gets(ch); //考虑到输入可能有空格 str.push_back(ch); } for(int i=0;i<n;i++)//对str中每一个字符串进行分析 { sum = 0; count = 0; temp = str[i]; for(int j = temp.length()-1;j>=0;j--) //从后往前， { if(temp[j]>='0'&&temp[j]<='9') { sum += (temp[j] -'0')*pow(10.0,count); count++; } } cout<<max_yinzi(sum)<<endl; } } return 0;}
运行时间：54ms
占用内存：492k
转载于:https://www.cnblogs.com/ttzz/p/10539126.html