纯小白，麻烦问下各位如何以最小的时间复杂度判断一个数是否为素数？感谢大家！（无视空间复杂度）
解释下算法即可，语言没有啥要求٩(๑•̀ω•́๑)۶
// 是素数返回true，不是素数返回false
bool isPrime(int n)
{
if (n == 0 || n == 1) { return false; }
if (n == 2) { return true; }
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
return true;
}
}
return false;
}
质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数
既然要求算法，穷举就不行了，涉及到数学知识了，如何尽量缩小循环范围，最简单的，如果这个数不是素数，那么除了它自身，能最大和他整除的数，一定小于等于它的一半，所以循环时，只取该数的一半就可以了。
所有大于10的质数中，个位数只有1,3,7,9。
根据以上条件应该可以大幅度缩短验证时间