1 条题解
-
0
题目分析
本题需要根据规则对一组整数进行特殊的分类和排序:
- 将所有数字分为素数和非素数(注意:1 既不是素数也不是合数,按非素数处理)。
- 对素数进行升序排序(从小到大)。
- 对非素数进行降序排序(从大到小)。
- 输出时,素数在前,非素数在后。
- 数据之间用空格分隔,最后一个数据后面有一个空格和一个换行符。
题目数据量非常小(n <= 99),排序算法用冒泡排序即可。
易错点
- **整数溢出问题:输入数据可能包含接近
int上限的数(如2147483647)。在判断素数时,计算i * i会导致int溢出。必须将isPrime函数参数和循环变量i定义为long long。 - 冒泡排序的边界:内层循环条件要写
j < n - 1 - i,每次遍历将最大值(或最小值)冒泡到末尾,可以减少不必要的比较。 - 输出格式:循环输出时统一加上空格,最后再输出一个换行符,即可满足“最后一个数据后面有一个空格和一个换行符”的严格要求。
参考代码 (C语言)
#include <stdio.h> // 判断素数的函数,参数和循环变量都要用 long long 防止溢出 int isPrime(long long num) { if (num <= 1) return 0; // 1 及以下不是素数 for (long long i = 2; i * i <= num; i++) { if (num % i == 0) return 0; } return 1; } // 冒泡排序:升序 void bubbleSortAsc(long long arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 交换 long long temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } // 冒泡排序:降序 void bubbleSortDesc(long long arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] < arr[j + 1]) { // 交换 long long temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { int n; long long arr[105]; long long primes[105]; long long nonPrimes[105]; int p_cnt = 0; int np_cnt = 0; // 读取 n if (scanf("%d", &n) != 1) { return 0; } // 读取 n 个整数并分类 for (int i = 0; i < n; i++) { scanf("%lld", &arr[i]); // 必须用 %lld 读入 long long if (isPrime(arr[i])) { primes[p_cnt++] = arr[i]; } else { nonPrimes[np_cnt++] = arr[i]; } } // 分别进行冒泡排序 bubbleSortAsc(primes, p_cnt); // 素数升序 bubbleSortDesc(nonPrimes, np_cnt); // 非素数降序 // 输出素数 for (int i = 0; i < p_cnt; i++) { printf("%lld ", primes[i]); // 必须用 %lld 输出 } // 输出非素数 for (int i = 0; i < np_cnt; i++) { printf("%lld ", nonPrimes[i]); } // 最后换行 printf("\n"); return 0; }
- 1
信息
- ID
- 634
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 117
- 已通过
- 24
- 上传者
吉公网安备22010402001496号