c++质数判断 使用sqrt

本文主要是介绍c++质数判断 使用sqrt，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果一个整数能被分解成2个数的乘积，那么小的那个数一定不会超过这个数的开方。

1不是质数。

8 => 2*4, 4*2
sqrt(8) =>3.xx

9 => 3*3
sqrt(9) =>3

11 =>
sqrt(11) =>3.xx

16 => 2*8, 4*4, 8*2
sqrt(16) =>4

18 => 2*9, 3*6, 6*3, 9*2
sqrt(18) =>4.xx

25 => 5*5
sqrt(25) =>5

使用sqrt函数求解质数

bool prime(int n){if(n==1) return false;for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;return true;
} 

不使用sqrt函数求解质数

bool prime(int n){if(n==1) return false;for(int i=2;i<n;i++)if(n%i==0)return false;return true;
} 

使用sqrt函数后，可以减少循环次数。

以判断 n=25 是否为质数为例子:
使用sqrt函数求解质数，最多循环次数为：4 次 => sqrt(n) - 1
不使用sqrt函数求解质数，最多循环次数为：23 次 => n - 2

结束。
仅学习。

这篇关于c++质数判断 使用sqrt的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---