试除法判定质数-526互联

其实质数也就是素数，这题比较简单，注意ai的数据类型为long long，和输入输出格式就欧克了，我就不详细解释了

直接上代码

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 1e3 + 4;

ll f(ll x)
{
	ll j;
	if (x == 1 || x == 0)  return 0; // 排除1和0的情况
	for (j = 2; j <=sqrt(x); j++) 
//不需要遍历到x,因为任何一个数都不可能分解成两个大于其平方根的数的乘积.肯定只能分解为一个大于或等于其平方根,另一个小于或等于其平方根.
	{
		if (x % j == 0) {
			return 0; //如果不是质数返回0，结束函数；
		}
	}
	return 1; //是质数就返回1；
}
int main()
{
	ll n, i, x;
	int k[N];
	scanf("%lld", &n);
	for (i = 0; i < n; i++) {
		scanf("%lld", &x);
		k[i] = f(x); //存结果
	}

	for (i = 0; i < n; i++)
	{
		if (k[i] == 1) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

关于为什么只需要遍历到一个数的平方根，因为如果一个数不是质数是合数，那么一定可以由两个自然数相乘得到，因子是成对出现的，就以64为例子，如果8之前就有因子，那么不是质数，后面就没有必要遍历了(x=9的话就81了).

本人蒟蒻，若有错误或不恰当的地方还望指出，感谢观看我的博客。