一、int is(int n) 的作用是什么？

1
2
3
4
5
6
int is(int n)
{
    for(int i=2;i*i<=n;i++)
        if(n%i==0) return 0;
    return 1;
}

👉 作用：判断一个整数 n 是否是质数（素数）

  • 返回 1：n 是质数
  • 返回 0：n 不是质数

所以它本质上是一个 质数判定函数。

二、为什么这样写能判断质数？

1️⃣ 质数的定义

质数：只能被 1 和自身整除的正整数（n ≥ 2）

2️⃣ 为什么从 i = 2 开始？

  • 1 肯定能整除任何数，没意义
  • 所以从 最小可能的因子 2 开始试

3️⃣ 为什么只枚举到 i * i <= n？

这是关键点 👇

数学原理：

如果 n 是合数：

1
n = a × b

那么：

  • 至少有一个因子 ≤ √n
  • 如果两个因子都 > √n，那么乘积会 > n（矛盾）

✅ 所以：

只要检查到 √n，就能确定 n 是否有因子

这也是为什么不用枚举到 n-1，可以大幅优化速度。

4️⃣ if(n % i == 0) return 0;

  • 找到一个能整除 n 的数
  • 说明 n 不是质数
  • 立刻返回 0（提前结束，节省时间）

5️⃣ return 1;

  • 循环结束都没找到因子
  • 说明 n 是质数

三、它在 solve() 里起什么作用？

1
2
for(int i=2;i<=10000;i++) 
    if(is(i)) a.push_back(i);

👉 这段代码的作用是：

  • 筛出 2 ~ 10000 之间的所有质数
  • 存进 vector<int> a

后面这一步：

1
pow(a[i],2) + pow(a[j],3) + pow(a[k],4)

说明题目要求的是：

质数² + 质数³ + 质数⁴

所以必须先把 质数集合 算出来，is() 就是为这个服务的。

四、为什么不用更简单的方法？

你可能会想到：

1
for(int i=2;i<n;i++)

❌ 这样是 O(n)
现在这种写法是 O(√n)，速度快很多。

在竞赛中：

  • n ≤ 10000
  • 判 10000 次质数
  • 这种写法完全没问题

五、这个函数有没有问题？（重要）

❌ 潜在 bug

1
is(1) 会返回 1（错误）

因为循环不进，直接 return 1

✅ 更严谨写法：

1
2
3
4
5
6
7
bool isPrime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0) return false;
    return true;
}

六、一句话总结（你记这个就够）

is(int n) 用来判断 n 是否是质数，通过枚举 2 到 √n 的因子，高效且常见，是竞赛中最基础的质数判定方法。