日志6

质数判断，只需扫描2~sqrt(n)之间的所有整数，依次检查他们能否整除n，若都不能整除，则n是质数，否则n是合数，此为试除法，时间复杂度为O(sqrt(n))，还需特判0和1，他们既不是质数也不是合数。代码如下：
#include<iostream>
using namespace std;
int isPrime(int n)
{
if(n<=1) return 0;
if(n==2) return 1;
if(n%2==0) return 0;
for(long long i=2;i*i<=n;i+=2)
{
if(n%i==0) return 0;
}
return 1;
}

int main()
{
long long n;
cin>>n;
if(isPrime(n)) cout<<"Yes\n";
else cout<<"No\n";
}