数组质数统计及同步输出代码的性能优化问询

API 探路者

2026-8-21

质数判断程序的性能优化方案

你的代码功能正常但超时的核心原因是质数判断的时间效率极低：原逻辑对每个数字n遍历从1到n的所有数统计因数，时间复杂度为O(n)，当n较大（如10^9级别）时，这个操作会消耗大量时间。以下是针对性的优化方案：

具体优化步骤

提前处理特殊值：
- 数字≤1时，直接判定为非质数（输出NO）；
- 数字=2时，直接判定为质数（输出YES）；
- 数字为偶数（能被2整除）时，直接判定为非质数（输出NO）。
缩小遍历范围：
质数判断只需遍历到√n即可——若n存在大于√n的因数，必然对应一个小于√n的因数，无需遍历到n本身。且由于已排除偶数，遍历从3开始，步长设为2，减少一半循环次数。
提前终止判断：
遍历过程中一旦找到能整除n的数，立即停止遍历并判定为非质数，避免无效计算。
边输入边处理（可选）：
无需预先存储所有数字，输入一个判断一个，节省内存同时减少数组读写开销。

优化后的代码

#include <cstdio>
#include <cmath> // 用于计算平方根

// 封装质数判断函数，返回1表示是质数，0表示非质数
int is_prime(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    
    int sqrt_n = (int)sqrt(n);
    // 只遍历奇数，步长为2
    for (int j = 3; j <= sqrt_n; j += 2) {
        if (n % j == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int rows, num, cn = 0;
    scanf("%d", &rows);
    
    for (int i = 0; i < rows; ++i) {
        scanf("%d", &num);
        if (is_prime(num)) {
            printf("YES\n");
            cn++;
        } else {
            printf("NO\n");
        }
    }
    printf("\n");
    return 0;
}