数学知识

试除法是整数分解整数分解)算法中最简单和最容易理解的算法。首次出现于意大利数学家斐波那契出版于1202年的著作。

给定一个合数 n （这里，n是待分解的正整数），试除法看成是用小于等于 sqrt(n) 的每个素数)去试除待分解的整数。如果找到一个数能够整除除尽，这个数就是待分解整数的因子。试除法一定能够找到n的因子。因为它检查n的所有可能的因子，所以如果这个算法“失败”，也就证明了n是个素数。试除法可以从几条途径来完善。例如，n的末位数不是0或者5，那么算法中就可以跳过末位数是5的因子。如果末位数是2，检查偶数因子就可以了。

#include<iostream>
#include<cstring>

using namespace std;

int n;

bool is_prime(int num)
{
    if(num<2) return false;//当数字小于2的时候，它一定不是质数
    for(int i = 2;i<=num/i;i++)//数字2和数字3都是质数，这里不会进入循环，从数字4开始进入循环
    {
        if(num%i==0) return false;//取模i，没有余数表示是质数
    }
    return true;
}

int main()
{
    scanf("%d",&n);


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

    return 0;

}