牛客网考研机试题集合：Problem C（求最大素因数）

本文主要是介绍牛客网考研机试题集合：Problem C（求最大素因数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

2^32大约有10位数

1）因为整数最多只有一个大于sqrt(n)的素数，先使用素数筛法，删选100000以内的所有素数。

2）将字符串中数字拼接，转化为整数（stoi函数），分解该整数的素因数，求出最大的。

3）由字符串获得整数也可以使用

sum=0;
if(isdigit(s[i]){sum=sum*10+s[i]-'0';
}

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=10000;vector<int> prime;
int mark[100001];
void init();
int maxPrime(int x);
int main() {int n;init();while(cin>>n) {string s;for(int i=0; i<n; i++) {cin>>s;int len=s.length();string tmp;for(int i=0; i<len; i++) {if(isdigit(s[i])) {tmp+=s[i];}}if(tmp.size()==0) {cout<<0<<endl;} else {int r=stoi(tmp);cout<<maxPrime(r)<<endl;}}}return 0;
}
void init() {fill(mark,mark+100001,0);for(int i=2; i<=100000; i++) {if(mark[i]==1) {continue;}prime.push_back(i);if(i>=1000) continue;for(int j=i*i; j<=100000; j+=i) {mark[j]=1;}}
}
int maxPrime(int x) {//set<int> ret;int ret;int size=prime.size();for(int i=0; i<size; i++) {while(x%prime[i]==0) {ret=prime[i];x/=prime[i];}if(x==1) {break;}}if(x!=1) {ret=x;}return ret;
}

 

这篇关于牛客网考研机试题集合：Problem C（求最大素因数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---