Problem C__牛客网

度小满内部推荐官

#include <iostream>
#include <algorithm>
using namespace std;
int strToint(string s){
    int length = s.length();
    int sum = 0;
    for(int i = 0;i < length;i++){
        if(s[i]>='0'&&s[i]<='9')
            sum = sum*10 + s[i]-'0';
    }
    return sum;
}
int sushu(int a){
    int max = 0;
    for(int i = 2;i*i <= a;i++){
        while(a%i==0){
            if(i>max)
                max = i;
            a/=i;
        }
    }
    return a>max?a:max;
}
int main(){
    int n;
    cin>>n;
    string s;
    for(int i = 0;i < n;i++){
        cin>>s;
        int a = strToint(s);
        //cout<<strToint(s);
        cout<<sushu(a)<<endl;
    }
    return 0;
}

发表于 2019-03-05 00:08:44 回复(6)

sunX&Y

/*
*用素数筛得到素数表，再在getMaxPrime中进行素数遍历会更快。
*/


#include<bits/stdc++.h>

using namespace std;

int n;

int getMaxPrime(int x)
{
    if(x == 0 || x == 1) return x;
    int h = sqrt(x);
    for(int i = 2;i <= h; i++)
    {
        while(x % i == 0) x /= i;
        if(x == 1) return i;
    }
    return x;
}

int getNumber(const string& s)
{
    int ans = 0;
    for(char c : s)
    {
        if(isdigit(c)) ans = ans*10 + c-'0';
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    string s;
    while(cin >> n)
    {
        for(int i = 0;i < n; i++)
        {
            cin >> s; cout << getMaxPrime(getNumber(s)) << "\n";
        }
    }
    return 0;
}

编辑于 2021-01-19 19:53:19 回复(0)

学术不精的霍尔系数

/*
开始的时候也是一头雾水，想着打表？几十亿的开销受不了，
看了下讨论区，提到了任何一个证书都可以分解为素数的乘积，了解！
如果以前写过类似的话应该很好懂，在check函数里，如果一个数n在检查他是否是素数的时候
其实只要检查到sqrt（n)即可，因为不可能两个因子都大于sqrt(n)；也就是说在我这么while
循环之后剩下的数肯定是素数，因为不是素数的话早就被除掉了



last：
LWQ   很高兴你能看到这里
*/
#include <stdio.h>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;

int lwqCheck(int n) {
	for(int i = 2;i*i<=n;i++){
        while(n%i==0)
            n/=i;
    }
    return n;
}

int main() {
	int n, num;
	scanf("%d", &n);
	char str[100];
	for (int i = 0; i < n; i++) {
		num = 0;
		scanf("%s", str);
		int len = strlen(str);
		for (int i = 0; i < len; i++) {
			if (isdigit(str[i])) {
				num *= 10;
				num += str[i] - '0';
			}
		}
		if (num == 0)
			printf("0\n");
		else {
			printf("%d\n",lwqCheck(num));
		}
	}
	return 0;
}

发表于 2019-09-09 16:09:07 回复(0)

走钢索的人_

// 质因子分解的依据：
// 任何合数都能被分解为若干个质数的乘积
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
  
using namespace std;
bool isPrim[100005];
void init()
{
    for(int i = 2;i<100005;i++)
    {
        isPrim[i] = true;
    }
    for(int i = 2;i<100005;i++)
    {
        for(int j = 2*i;j<100005;j+=i)
        {
            isPrim[i] = false;
        }
    }
}
bool pd(int x)
{
    for(int i = 2;i<=sqrt(x);i++)
    {
        if(x % i == 0)
        return false;
    }
    return true;
}
void outPut(int x)
{
    int maxx = -1;
    for(int i = 2;i*i<=x;i++)
    {
        while(x % i == 0)
        {
            x /= i;
            maxx = max(maxx,i);
        }
    }
    if(pd(x))
    {
        maxx = max(x,maxx);
    }
    cout << maxx << endl;
}
int getInt(string s)
{
    int ans = 0;
    for(int i = 0 ;i<s.length();i++)
    {
        if(s[i] >= '0' && s[i] <= '9')
        {
            ans *= 10;
            ans += (s[i] - '0');
        }
    }
    return ans;
}
int main()
{
    init();
    int n;
    while(cin >> n)
    {
        for(int i = 0 ; i<n;i++)
        {
            string s;
            cin >> s;
            int ans = getInt(s);
            if(ans == 0 || ans == 1)
            {
                cout << 0 << endl;
                continue;
            }
            if(pd(ans))
            {
                cout << ans << endl;
                continue;
            }
            outPut(ans);
        }
    }
}

发表于 2019-03-04 22:24:35 回复(0)

C++

我狂练考研机试题

#include <iostream>
#include <string>
using namespace std;

int main(){
    int m;
    cin >> m;
    while(m--){
        string str, num;
        cin >> str;
        for(int i=0; i<str.size(); ++i){
            if(str[i]>='0' && str[i]<='9'){
                num.push_back(str[i]);
            }
        }
        int n;
        if(num.empty()) {
            cout << "0" << endl;
            continue;
        }else{
            n = stoi(num);
        }
        for(int i=2; i*i<=n; ++i){
            while(n%i==0) n /= i;
        }
        cout << n << endl;
    }
}

编辑于 2024-03-15 20:04:08 回复(0)

C++

无问西东gmy

#include <cmath>
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

bool isPrime(int num) { //判断是否为素数
    if (num < 2) {
        return false;
    }
    int bound = sqrt(num);  //判断边界
    for (int i = 2; i <= bound; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    while (cin >> n) {
        while (n--) {
            string str1, str2;          //字符序列用字符串（string）表示
            cin >> str1;
            for (const auto& ch : str1) {
                if (ch >= '0' && ch <= '9') {
                    str2 += ch;
                }
            }
            if (str2 == ""              //字符序列中没有数字
                    || str2 == "0") {   //或者找出的整数为0
                cout << 0 << endl;
                continue;
            }
            int num = atoi(str2.c_str());
            if (isPrime(num)) {         //如果是素数，则最大因子为自身
                cout << num << endl;
                continue;
            }
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    while (num % i == 0) {
                        num /= i;
                    }
                }
            }
            cout << num << endl;
        }
        cout << endl;
    }
    return 0;
}

发表于 2024-02-13 23:00:33 回复(0)

C++

EvenLiang111

// 天，花了好久才弄出来  本以为很简单的，但是还是要考虑i和a/i分别是不是素数的问题
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;

bool isSushu(int a)
{
    for(int i = 2;i*i<=a;i++)
    {
        if(a%i==0)
            return false;
    }
    return true;
}

int main()
{
    int n;
    cin>>n;
    for (int i=0;i<n;i++)
    {
        string str,numStr;
        cin>>str;
        for(int i=0;i<str.size();i++)  //遍历整数
        {
            if(str[i]>='0'&&str[i]<='9')
            {
                numStr+=str[i];
            }
        }
        // 去除前导0
        int idx = 0;
        while(numStr[idx]=='0')
        {
            idx++;
        }
        numStr = numStr.substr(idx);
        // 转成int
        int a = 0;
        for(int i=0;i<numStr.size();i++)
        {
            a = a*10+numStr[i]-'0';
        }
        // 求最大素因子
        int maxFac = 1;
        for(int i=1;i<=sqrt(a);i++)
        {
            if(a%i==0)
            {
                if (isSushu(a/i))
                    maxFac = a/i;
                else if(isSushu(i))
                    maxFac = i;
            }
        }
//         cout<<st.size()<<endl;
        if(numStr.empty())
            maxFac = 0;
        if(maxFac == 1)
            maxFac = a;

        cout<<maxFac<<endl;
    }
}

发表于 2022-07-15 11:11:53 回复(0)

menao

def isPrime(n):
    for i in range(2,int(n ** 0.5)+1):
        if n % i == 0:
            return False
        return True
def maxPrime(n):
    index = 2
    maxPri = None
    while index <= n:
        if isPrime(n) and n % index == 0:
            n /= index
            maxPri = index
        index += 1
    return maxPri

while True:
    try:
        n = int(input())
        strings = []
        for i in range(n):
            string = input()
            strs = ''
            for j in string:
                if j.isdigit():
                    strs += j
            if strs:
                strings.append(maxPrime(int(strs)))
            else:
                strings.append(0)
        print(strings)


    except:
        break

他给我超时了

发表于 2021-04-27 19:45:29 回复(0)

伏地魔盖茨

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int num;
    cin>>num;
    string c[num];
    getchar();
    for(int i=0;i<num;i++)
        getline(cin,c[i]);
    for(int i=0;i<num;i++)
    {
        long int a=0;
        for(int j=0;j<c[i].length();j++)
        {
            if(c[i][j]>='0'&&c[i][j]<='9')
                a=a*10+c[i][j]-'0';
        }
        if(a==0)
        {
            cout<<"0"<<endl;
            continue;
        }
        int max=0;
        while(a>0)
        {
        	for(int i=2;i<=sqrt(a);i++)
        	{
        		if(a%i==0)
        		{
        			a=a/i;
        			if(max<i)
        				max=i;
        			break;
				}
				if(i==int(sqrt(a)))
					if(max<a)
        			{	
        				max=a;
        				a=0;//退出循环 
					}
			}
		}
		cout<<max<<endl;   
    }
}

编辑于 2021-03-06 16:45:42 回复(0)

被风吹落的水果

递归

int help(int n) {
	int i = sqrt(n);
	while (n%i) 
		i--;
	return i == 1 ? n : max(help(i), help(n / i));
}
int main(){
    int m;
    cin>>m;
    while(m--){
    string str = "";
	cin >> str;
	int n = 0;
	for (auto ch : str)
		if (isdigit(ch))
			n = n * 10 + ch - '0';
	cout << (n? help(n):0)<<endl; 
    }
}

发表于 2021-03-05 21:08:46 回复(0)

C/C++

夜巷

#include<stdio.h>
#include<string.h>
double stringToNum(char c[]){
	int length = strlen(c);
	double add = 0;
	for(int i = 0; i < length; i++){
		if(c[i] >= '0' && c[i] <= '9')
		add = add * 10 + c[i] -'0';
	}
	return add;
}
int maxPrime(int num){
	int max = 0;
	
	for(int i = 2; i * i <= num; i++){
		while(num % i == 0){
			if(i > max) max = i;
			num /= i;
		}
	}
	//printf("%d",num);
	return num>max?num:max;
}
int main(){
	char string[100] = {0};
	int n;
	int num = 0;
	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		scanf("%s",&string);
		int num = stringToNum(string);
		printf("%d\n",maxPrime(num));
        num = 0;
	}
}

发表于 2021-03-03 17:05:01 回复(0)

C/C++

纠结offer的菜狗

#include<iostream>
#include<string>
#include<math.h>
using namespace std;

int MaxPrime(int n)
{
    for(int i = 2;i <= int(sqrt(n));i++)
    {
        while(n % i == 0) n /= i;
    }
    return n;
}

int main()
{
    int n,sum;
    string s;
    while(cin >> n)
    {
        while(n--)
        {
            sum = 0;
            cin >> s;
            for(int i = 0;i < s.size();i++)
            {
                if(s[i] >= '0' && s[i] <= '9') sum = 10 * sum + s[i] - '0';
            }
            cout << MaxPrime(sum) << endl;
        }
    }
    return 0;
}

发表于 2021-02-27 23:05:52 回复(0)

Java

Leida_pfy

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-- > 0) {
            String str = scanner.next();
            int sum = jieGuo(str);
            System.out.println(res(sum));
        }
    }

    public static int res(int sum) {
        int prime = 0;
        for (int i = 2; i* i <= sum; i++) {
            while(sum % i == 0) {
                prime = Math.max(prime,i);
                sum /= i;
            }
        }
        return sum;
    }
    public static int jieGuo(String str) {
        int sum = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                sum = sum * 10 + str.charAt(i) - '0';
            }
        }
        return sum;
    }
}

发表于 2021-01-20 10:06:32 回复(0)

Java

一笑而过19

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            for(int i = 0; i < n; i++){
                String s = sc.next();
                int num = getValidNum(s);
                int res = getMaxPrimeFactor(num);
                System.out.println(res == -1 ? num : res);
            }
        }
        sc.close();
    }
    private static int getValidNum(String s){
        if(s == null || s.length() == 0) return 0;
        int res = 0;
        int n = s.length();
        for(int i = 0; i < n; i++){
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                int cur = s.charAt(i) - '0';
                res = res * 10 + cur;
            }
        }
        return res;
    }
    private static int getMaxPrimeFactor(int num){
        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                while(num % i == 0){
                    num /= i;
                }
            }
        }
        if(num > 1) return num;
        return -1;
    }
}

发表于 2020-08-09 18:17:39 回复(0)

韩伟业

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    public static void main(String args[])
    {
        Scanner in=new Scanner(System.in);
        while(in.hasNext())
        {
            int n=in.nextInt();
            in.nextLine();
            String str[]=new String[n];
            for(int i=0;i<n;i++)
            {
                str[i]=in.nextLine();
            }

            for(int i=0;i<n;i++)
            {
                char c[]=str[i].toCharArray();
                char b[]=new char[100];
                int k=0;
                for(int j=0;j<c.length;j++)
                {
                    if(c[j]>='0'&&c[j]<='9')
                    {
                        if(c[j]=='0'&&k==0)
                        {
                            continue;
                        }
                        b[k]=c[j];
                        k++;
                    }
                }
                if(k!=0)
                {
                    int res=0;
                    for(int x=0;x<k;x++)
                    {
                        res=res+(b[x]-'0')*(int)(Math.pow(10,k-x-1));
                    }
                    System.out.println(qinum(res));
                }
                else{
                    System.out.println("0");
                }
            }

        }
    }
    public static int qinum(int a)
    {
        int i=2;
        while(i*i<=a)
        {
            if(a%i==0)
            {
                a=a/i;
            }else{
                i++;
            }
        }
        int num=a;
        return num;
    }
}

发表于 2020-07-16 20:37:43 回复(0)

C/C++

liangweixu

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e6+7;
int vis[maxn]={0},isp[maxn]={0};
int len=0;
int strToint(string s){ //字符串找数字
int length = s.length();
int sum = 0;
for(int i = 0;i < length;i++){
if(s[i]>='0'&&s[i]<='9')
sum = sum*10 + s[i]-'0';
}
return sum;
}
void prime(int a) //找出最大素数
{
for(int i=2;i<=a;i++){
if(!vis[i]) isp[len++]=i;
for(int j=0;j<len&&i*isp[j]<=maxn;j++){
vis[i*isp[j]]=1;
if(i%isp[j]==0) break;
}
}
for(int i=len-1;i>=0;i--) //且这个素数是它的最大因子
{
if(a%isp[i]==0)
{
cout<<isp[i]<<endl;
break;
}
}

}
int main()
{ int n;
cin>>n;
string s;
for(int i = 0;i < n;i++){
cin>>s;
int a = strToint(s);
prime(a);
}
}

发表于 2020-07-15 12:34:18 回复(2)

刘涛_go

【解题思路】从字符串中，依据每个字符的ascii码是否在‘0’~‘9’内来提取数字。随后，考察数字中的质因数。注意，一个数字N至多只有一个质因数大于sqrt(N)，否则两个这么大的质因数乘起来就大于N了。因此，只需要遍历所有小于等于sqrt(N)的质数，寻找其中最大的可以整除N的数M，同时将N约去所有小于等于sqrt(N)的质因数。这时，要么N被约成1，这时结果取前面的M；要么N还剩一个大于sqrt(N)的质因数P，这时结果取P。

为了节省时间，所有的用例共用一张素数表，这样就不用反复寻找前面的小素数了。

【参考答案】

#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <vector>
#define fin cin
using namespace std;

int findMaxFactor(int num, vector<int>& v)
{
    int result = 0;
    if(num <= 3){
        result = num;
    }
    else{
        int remain = num;
        for(int i=0; i < v.size() && v.at(i) <= sqrt(num); i++){
            if(remain % v.at(i) == 0){
                result = v.at(i);
                while(remain % v.at(i) == 0){
                    remain /= v.at(i);
                }
            }
            if(remain <= 1){
                break;
            }
        }
        if(v.back() < sqrt(num)){
            for(int i=v.back()+1; i <= sqrt(num); i++){
                bool isPrime = true;
                for(int j=0; v.at(j) <= sqrt(i); j++){
                    if(i % v.at(j) == 0){
                        isPrime = false;
                        break;
                    }
                }
                if(isPrime){
                    v.push_back(i);
                    if(remain % i == 0){
                        result = i;
                        while(remain % i == 0){
                            remain /= i;
                        }
                        if(remain <= 1){
                            break;
                        }
                    }
                }
            }
        }
        if(remain > sqrt(num)){
            result = remain;
        }
    }
    return result;
}

int main()
{
    // ifstream fin("1.in");
    int n;
    string str;
    fin >> n;
    vector<int> v;
    v.push_back(2);
    v.push_back(3);
    for(int i=0; i<n; i++){
        fin >> str;
        string mystr = "0";
        for(int ch=0; ch < str.size(); ch++){
            if(str.at(ch) >= '0' && str.at(ch) <= '9'){
                mystr += str.at(ch);
            }
        }
        int num = stoi(mystr);
        cout << findMaxFactor(num, v) << '\n';
    }
    // fin.close();
    return 0;
}

发表于 2020-07-12 14:47:33 回复(0)

Python

把伤害当做酒窝

刚学编程不久。用python解的这道题，结果正确，就是超时了。

def zhishu(n):
    if n >= 2:
        lis = []
        for i in range(1, n+1):
            if n % i == 0:
                lis.append(i)
        if len(lis) == 2:
            return n
    else:
        pass
num = []
for i in range(int(input())):
    digit = []
    string = input()
    for j in string:
        if j.isdigit():
            digit.append(j)
    num.append(digit)
num = [''.join(elment) for elment in num]
convert = []
for e in num:
    if e != '':
        convert.append(int(e))
    else:
        convert.append(0)
for k in convert:
    if k == 0:
        print(0)
    else:
        zhiyinshu = []
        for m in range(1, k):
            if zhishu(m) == m and k % m == 0:
                zhiyinshu.append(m)
        print(max(zhiyinshu))

发表于 2020-05-05 20:53:17 回复(0)

inf__

#include<iostream>
#include<vector>
#include<math.h>

using namespace std;

vector<string> getStrs(int n){
    vector<string> strs;
    string str;
    for(int i=0; i<n; i++){
        cin>>str;
        strs.push_back(str);
    }
    return strs;
}

int getNum(string str){
    int num = 0;
    for(int i=0; i<str.size(); i++){
        if(str[i] >= '0' && str[i] <= '9'){
            num = num*10 + str[i] - '0';
        }
    }
    return num;
}

int get_max_prime_factor(int num){
    int max_p = 0;
    //除去所有偶数的因子
    while(num % 2 == 0){
        num /= 2;
        max_p = 2;
    }
    //上面的while循环结束后num一定是个奇数
    //直接i += 2跳过所有的偶数
    for(int i=3; i<=sqrt(num); i += 2){
        while(num % i == 0){
            num /= i;
            max_p = i;
        }
    }
    return max(max_p, num);
}

int main(){
    int n;//有n个字符串
    cin>>n;
    vector<string> strs = getStrs(n);
    for(string str : strs){
        int num = getNum(str);
        if(num == 0){
            cout<<num<<endl;
        }else{
            int max_p = get_max_prime_factor(num);
            cout<<max_p<<endl;
        }
    }
    return 0;
}

编辑于 2020-05-04 12:09:07 回复(0)

C/C++

不偷不抢安度因_

 #include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        getchar();
        while(n--)
        {
            unsigned int data = 0;
            char ch;
            while((ch = getchar()) != '\n')
            {
                if(isdigit(ch))
                    data = data * 10 + ch - '0';
            }
            unsigned int i, div = data, div2 = 0;
            for(i = 2; i * i <= div; i++)
            {
                while(div % i == 0)
                {
                    div2 = i;
                    div /= i;
                }
            }
            printf("%u\n", div > div2 ? div : div2);
        }
    }

    return 0;
}

编辑于 2020-04-24 14:43:23 回复(0)

Problem C

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题