前言

正常判断一个数，要循环除以每个小于自身且大于1的整数，若余数为0，则为非素数。
但是这样太慢，时间复杂度为o ( n ) ，判断大量的绝对不行

解决办法

返回1是素数

int prime(int p)
{
	if (p == 2 || p == 3)
	{ 
		return 1; 
	}
	if (p % 6 != 1 && p % 6 != 5)
	{ 
		return 0; 
	}
	for (int i = 5; i <= floor(sqrt(p)); i += 6)
	{
		if (p%i == 0 || p % (i + 2) == 0)
		{ 
			return 0;
		}
	}
	return 1;
}

第一部分

if (p == 2 || p == 3)
	{ 
		return 1; 
	}

先将2和3两个质数给排除出去

第二部分

if (p % 6 != 1 && p % 6 != 5)
	{ 
		return 0; 
	}

	for (int i = 5; i <= floor(sqrt(p)); i += 6)
	{
		if (p%i == 0 || p % (i + 2) == 0)
		{ 
			return 0;
		}
	}
	return 1;

所有大于3的数都可以写成 6x+1，6x+2，6x+3，6x+4，6x+5

😕 6x+2=2（3x+1）--可以被整除，非质数
😕 6x+3=3（2x+1）--可以被整除，非质数
😕 6x+4=2（3x+2）--可以被整除，非质数
🎉️ 只有（6x+1），（6x+5）不可被整除

👀️ 所以先筛选出去模除6不为1或者5的所有数，且一定为非质数

因为在这之前已经判断了6x+2，6x+3，6x+4
最后一个循环判断这个数会不会被6x+1，6x+5
所以5开始步进为2

6x+1=i + 2
6x+5=i

🚀️ 若存在整出返回0，非质数，否则是返回1是质数