AcWing 866. 试除法判定质数
原题链接
简单
作者:
呼和
,
2019-08-30 01:00:12
,
所有人可见
,
阅读 715
除了2和3 其他的质数都在6的倍数的两边
/*****************************************
Problem Name :
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 100010;
bool flag(int x)
{
if(x == 1)
return false;
if(x == 2 || x == 3)
return true;
if(x%6 != 1 && x%6 != 5)
return false;
for(int i = 3 ; i*i <= x ; i+=2)
if(x % i == 0)
return false;
return true;
}
int main()
{
int t;
cin >> t;
while(t--)
{
int x;
cin >> x;
if(flag(x))
cout << "Yes\n";
else
cout << "No\n";
}
}