解题报告

撰写人：朱子轩

题意分析

质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。现在需要编写一个程序，判断输入的数是否为质数。

难度等级
★☆☆☆☆

解题思路

见到这个题，少不了筛素数的板子

首先给大家介绍几个筛素数的板子
1.根据定义：素数就是一个数除了1和他本身没有其他因数的数叫做质数。 于是我们对于一个n,可以可以从2枚举到n−1，从而判断这个数是不是质数。
优化1：
bool prime1(int x)
{
	if(x<2) return false;
	if(x==2) return true;
	for(int i=2;i<=x;i++)
		if(x%i==0) return false;
	return true;
}

我们不难发现n的因数是成对出现的，所以对于任何一个整数n，我们只需要从1枚举到根号下n就可以了。
所以这个的时间复杂度就是O（根号下n）

bool prime2(int x)//O(根号下n)
{
	if(x<2) return false;
	if(x==2) return true;
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0) return false;
	return true;
}

此方法的时间复杂度就大大减小，为O（三分之
根号下n）

bool quick_prime(int x)//O(三分之根号下n) 
{
	if(x==2||x==3) return true;
	if(x%6!=1&&x%6!=5) return false;
	for(int i=5;i<=sqrt(x);i+=6)
		if(x%i==0||x%(i+2)==0) return false;
	return true;
}

小结：在对于素数的判断时，一般用第一种的优化方法就可以了，但是如果遇到了毒瘤出题人，最好是用第二种方法。
那本题的思路就出来了，先判断这个数是不是素数，

ull prime(ull x){
	if(x==2||x==3) return 1;
	if(x%6!=1&&x%6!=5) return 0;
	for(int i=5;i<=sqrt(x);i+=6)
	if(x%i==0||x%(i+2)==0) return 0;
	return 1;
}
ull simple_prime(ull k){
	if(!prime(k)){
	if(k%2!=0&&k%5!=0&&k%3!=0){
		return 1;
		}
	}
	return 0;	
}
if(prime(n)||simple_prime(n))
{
		if(n==1) cout<<"No<<endl;
		else cout<<"Yes"<<endl;
} 
else cout<<"No"<<endl;

cpp
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll p(ll x){
	if(x==2||x==3) return 1;
	if(x%6!=1&&x%6!=5) return 0;
	for(int i=5;i<=sqrt(x);i+=6)
	if(x%i==0||x%(i+2)==0) return 0;
	return 1;
}
ll s(ll k){
	if(!p(k)){
	if(k%2!=0&&k%5!=0&&k%3!=0){
		return 1;
		}
	}
	return 0;	
}
int main()
{
	int n;
	cin>>n;
	if(p(n)||s(n))
	{
		if(n==1) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	} 
	else cout<<"No"<<endl;
	return 0;
}