跳转至

试除法判质数

质数一定都大于等于 2。

给点一个正整数 \(n\)：

  • 若 \(n\) 是质数，则 \(n = 1 * n\)；
  • 若 \(n\) 不是质数，则 \(n\) 可以分解为两个正整数 \(x，\frac{n}{x}\) 的乘积。

我们令 \(x\) 是 \(x，\frac{n}{x}\) 两者中最小的：

  • 若 \(x = \frac{n}{x}\)，则有 \(x = \frac{n}{x} = sqrt(n)\)
  • 若 \(x < \frac{n}{x}\)，则有 \(x < sqrt(n), \frac{n}{x} > sqrt(n)\)

我们只需要从 \(2\) 一直遍历到 \(sqrt(n)\) 就可以找出这个小的 \(x\)，如果找不到，就说明 \(n\) 是质数。

因此每判断一次质数的「时间复杂度」最坏为 \(sqrt(n)\)。

由于运算操作 \(sqrt(n)\) 的「时间消耗大」，我们采用 i <= n / i 的形式代替 i <= sqrt(n)。

时间复杂度最坏为：\(O(sqrt(n))\)，此时 \(n\) 为质数。

bool is_prime(int n)
{
    if (n <= 2) return n == 2;
    for (int i = 2; i <= n / i; i ++)
        if (n % i == 0) return false;
    return true;
}
866. 试除法判定质数

给定 \(n\) 个正整数 \(a_i\)，判定每个数是否是质数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

int n;

bool is_prime(int n)
{
    if (n <= 2) return n == 2;
    for (int i = 2; i <= n / i; i ++)
        if (n % i == 0) return false;
    return true;
}

void solve(void)
{
    scanf ("%d", &n);
    while (n --)
    {
        int t; scanf ("%d", &t);
        if (is_prime(t)) puts("Yes");
        else puts("No");
    }
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}