试除法判定质数：深入探索与代码分析

「爱情、让人受尽委屈。」 2024-02-20 08:49 53阅读 0赞

## **试除法判定质数：深入探索与代码分析** ##

质数它是只有 1 和其自身两个正因子的自然数，例如：2、3、5、7 等。这篇文章将探讨如何使用试除法来判定一个数字是否为质数，并通过提供的代码来进行详细的分析。

**1. 试除法是什么？**

试除法是判定质数最直观、简单的方法。它的基本思想是：要确定一个数 `n` 是否为质数，我们可以尝试去除 `2` 到 `sqrt(n)` 之间的所有整数。如果 `n` 可以被这其中的任何一个数整除，那么 `n` 就不是一个质数。

**2. 为什么只除到 `sqrt(n)`？**

一个很好的观察是：如果 `n` 不是质数，并且它有一个因子大于 `sqrt(n)`，那么它必定有一个小于或等于 `sqrt(n)` 的因子。因此，我们只需要检查 `2` 到 `sqrt(n)` 范围内的数。

为了使代码更高效，我们用 `i <= x / i` 代替 `i <= sqrt(x)` 来避免使用昂贵的平方根计算。

**代码分析**：

bool is_prime(int x)
    {
        
        if (x < 2) return false;  // 小于2的数不是质数
        for (int i = 2; i <= x / i; ++ i)  // 从2遍历到x的平方根
        {
        
            if (x % i == 0) return false;  // 如果x能被i整除，那么x不是质数
        }
        return true;  // 如果循环完成，x就是质数
    }

此函数的核心就是上面描述的试除法。它首先排除小于2的数，然后尝试除以每一个小于其平方根的正整数。

**3. 主函数的功能**

主函数首先读入一个数 `n`，表示接下来有 `n` 个数需要检查是否为质数。然后，对于这 `n` 个数，它调用 `is_prime` 函数并输出结果。

int main()
    {
        
        int n;
        cin >> n;
        while(n --)  // 遍历这n个数
        {
        
            int t;
            cin >> t;
            if (is_prime(t)) cout << "Yes\n";  // 如果t是质数，输出"Yes"
            else cout << "No\n";  // 否则输出"No"
        }
        return 0;
    }