黑马程序员技术交流社区

标题: 【上海校区】判断一个数是否为素数（质数） [打印本页]

---

作者: 梦缠绕的时候    时间: 2020-5-8 09:00
标题: 【上海校区】判断一个数是否为素数（质数）
质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

int isprime(int x) {
    if (x < 2) return false; // 小于2的数都不是质数
    for (int i = 2; i < x; i++)
        if (x % i == 0) return false;
    return true;
}
显然这个算法的复杂度为O(n)。

我们知道，一个数如果可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)。所以，循环没有必要从2到x−1，只需要从2到sqrt(n)就好了，那么这个算法的时间复杂度就为O(sqrt(n))。

int isprime(int x) {
    if (x < 2) return false; // 小于2的数都不是质数
    for (int i = 2; i <= int(sqrt(x)); i++) // 从2到sqrt(x)
        if (x % i == 0) return false;
    return true;
}
当然，这个算法还可以继续优化，我们可以判断2是不是这个数的约数，然后就可以从3开始循环到sqrt(n)了，每次循环i+2，那么这个算法的复杂度就为O(sqrt(n)/2)。

int isprime(int x) {
    if (x < 2) return false; // 小于2的数都不是质数
    if (x != 2 && x % 2 == 0) return false; // 不是2且能被2整除的数都不是质数
    for (int i = 3; i <= int(sqrt(x)); i += 2) // 每次循环加2
        if (x % i == 0) return false;
    return true;
}
即使是上述的算法，在遇到很大的数字(n≥100,000,000)的时候，还是很慢。
那还有没有更快的算法呢？答案是有的，埃拉托斯特尼筛法就是其中之一。

我们可以把从2到maxn的数储存为一张表，例如bool prime[MAXN];。
然后我们一词遍历这个数组，把i的倍数从数组中去掉，这样我们就得到了一张从2到maxn的质数的表。
需要判断一个数是否为质数的时候只需要查询这张表就可以了，例如if (prime) // 你的操作。

void getPrime(int maxn) {
    for (int i = 0; i <= maxn; i++) prime = 1; // 全部定义为质数
    prime[0] = prime[1] = 0;
    for (int i = 2; i <= maxn; i++) {
        if (!prime) continue;
        for (int j = i * 2; j <= maxn; j += i) prime[j] = 0; // i的倍数标记为合数
    }
}
素数的四种判断方法、实现及比较：https://blog.csdn.net/zhanshen112/article/details/90574455

以上内容转载自网络

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2