题记(38)--整数的最大素因子

目录

一、题目内容

二、输入描述

三、输出描述

四、输入输出示例

五、完整C语言代码

---

一、题目内容

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

二、输入描述

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

三、输出描述

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

四、输入输出示例

输入：

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

输出：

13
857
0

---

五、完整C语言代码

AC代码~
#include<stdio.h>
#include<math.h>
int IsPrime(long long int n) {if (n <= 1)return 0;for (int i = 2; i * i <= n; i++) {if (n % i == 0)return 0;}return 1;
}int main() {int m;char s[101];int a[100];scanf("%d", &m);char c = getchar();for (int count = 0; count < m; count++) {gets(s);int i = 0;int j = 0; // 数字数组下标long long int sum = 0;while (s[i] != '\0') {if ('0' <= s[i] && s[i] <= '9') {a[j] = s[i] - '0';j++;}i++;}for (int k = 0; k < j; k++)sum = sum * 10 + a[k];if (sum == 0)printf("0\n");else {int max = 2;for (int k = 1; k <= sqrt(sum); k++) {if (sum % k == 0 ) {if (IsPrime(sum / k)) {max = sum / k;break;}if (IsPrime(k))max = k;}}printf("%d\n", max);}}return 0;}