求整数的最大质因子

时间：2022-12-05 00:21:42

题目描述

对于给定的字符序列，从左至右将所有的数字字符取出拼接成一个无符号整数（字符序列长度小于100，拼接出的整数小于2^31,），计算并输出该整数的最大素因子（如果是素数，则其最大因子为自身）

输入描述:

有多组数据，输入数据的第一行为一个正整数，表示字符序列的数目，每组数据为一行字符序列。

输出描述:

对每个字符序列，取出所得整数的最大素因子，若字符序列中没有数字或者找出的整数为0，则输出0，每个整数占一行输出。
示例1

输入

复制 
3
sdf0ejg3.f?9f
?4afd0s&2d79*(g
abcde

输出

复制 
13
857
0
分析：本题目有两个要点，一是如何将字符串中的数字提取出来并计算成对应的整数
而是求出这个数的最大质因子
需要注意的是：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

 
标签：

相关文章