试除法判断质数

质数

什么是质数：存在一个数 $n \, (n > 1)$ ，若 $n$ 只能被 $1$ 和 $n$ 整除，不再有其他的因数，称为质数（素数），否则称为合数。若 $n \le 1$ ，$n$ 既不是质数，也不是合数。

判定质数——试除法

从定义出发，枚举每个 $i \ (3 \le i \le n - 1)$ ，若 $i|n$（ $n$ 能被 $i$ 整除 $n \ \% \ i = 0$），则 $n$ 不是质数。时间复杂度是 $O(n)$ 的。

如果 $d|n$ （ $d$ 整除 $n$ ） ，那么 $\frac{n}d|n$ （ $n$ 除 $d$ 的商也能整除 $n$ ）的。比如 $d = 3, n = 13$ 的时候，$3$ 可以整除 $12$ ，$\frac{12}3$ 也可以整除 $12$ 。可以发现 $n$ 的约数都是成对出现的，我们在枚举的时候，可以只枚举每一对中较小的那个： $d \le \frac{n}d$ ，化简后 $d^2 \le n, d \le \sqrt{n}$ 。时间复杂度从 $O(n)$ 降到了 $O(\sqrt{n})$ 。

题目描述

给定 $n$ 个正整数 $a_i$，判定每个数是否是质数。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个正整数 $a_i$。

输出格式

共 $n$ 行，其中第 $i$ 行输出第 $i$ 个正整数 $a_i$ 是否为质数，是则输出 Yes，否则输出 No。

数据范围

$1≤n≤100$, $1≤a_i≤2^{31}-1$

样例

输入样例：

2
2
6

输出样例：

Yes
No

代码

暴力版 $O(n)$

暴力做法，时间复杂是 $O(n)$ 的。

C++

#include <iostream>

using namespace std;

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

int main()
{
    int T;
    cin >> T;
    while ( T-- )
    {
        int n;
        cin >> n;
        cout << (is_prime(n) ? "Yes" : "No") << endl;
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T-- > 0 )
        {
            int n = in.nextInt();
            System.out.printf("%s\n", is_prime(n) ? "Yes" : "No");
        }
    }
    
    public static boolean is_prime(int n)
    {
        if ( n < 2 ) return false;
        for ( int i = 2; i < n; i ++ )
            if ( n % i == 0 ) return false;
        return true;
    }
}

优化版 $O(\sqrt{n})$

优化后，时间复杂是 $O(\sqrt{n})$ 的。

for ( int i = 2; i <= n / i; i ++ )，这里可能有下面几种写法

for ( int i = 2; i <= sqrt(n); i ++ )。不推荐，每次循环后，都会执行判断条件，所以每次都会调用sqrt()函数，比较耗时间。

for ( int i = 2; i * i <= n; i ++ )。存在数据溢出的风险。

C++

#include <iostream>

using namespace std;

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

int main()
{
    int T;
    cin >> T;
    while ( T-- )
    {
        int n;
        cin >> n;
        cout << (is_prime(n) ? "Yes" : "No") << endl;
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T-- > 0 )
        {
            int n = in.nextInt();
            System.out.printf("%s\n", is_prime(n) ? "Yes" : "No");
        }
    }
    
    public static boolean is_prime(int n)
    {
        if ( n < 2 ) return false;
        for ( int i = 2; i <= n / i; i ++ )
            if ( n % i == 0 ) return false;
        return true;
    }
}