质数的多种判断方法_找素数 i*i 和sqrt谁快

作者：从前慢现在也慢 | 2024-02-10 19:26:46

踩

找素数 i*i 和sqrt谁快

一类问题：判定一个整数n(n>1)是否为素数。
算法1:

直接根据素数的定义枚举i
从2到(n−1)，如果n%i==0n为合数。
时间复杂度：O(n)

**  
bool is_prime(int n) {
    int i;
    for(i = 2; i < n; i++)
        if(n % i == 0) return false;
    return true;
} 
**1
2
3
4
5
6
7
8

算法2:
大部分人都知道的比较快的方法：判断从2到sqrt(n)是否存在其约数，
时间复杂度O(sqrt(n))

bool is_prime(int n) {
int i;
for(i = 2; i * i <= n; i++)
if(n % i == 0) return false;
return true;

算法3：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/75268

**质数的多种判断方法**_找素数 i*i 和sqrt谁快