前言

最近闲来无事，刷刷题，碰到这样一个题目：

需求：要求实现一个判断素数的简单函数
相关信息：素数就是只能被1和自身整除的正整数。注意：1不是素数，2是素数。
输入：任意整数
输出：1——素数;0——非素数.

第一反应是将大于等于2的输入整数循环除以每个小于自身且大于1的整数，若余数为0，则为非素数。
再一想，这样做速度实在太慢，时间复杂度为$o(n)$。故在网上水了一波，看看到底有没有更快速的算法。

解决方案

方案1

方案1，就是上述方法，代码如下：

int prime(int p)
{
   
   
	if(p<=1)
	{
   
   
		return 0;
	}
	for(int i=2;i<p;i++)
	{
   
   
		if(p%i==0)
		{
   
   
			return 0;
		}
	}
	return 1;
} 

方案2

方案2是方案1的改进方案，该方案基于以下客观事实：一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。

int prime(int p)
{
   
   	
	if(p<=1)
	{
   
   
		return 0