C++判断质数的方法

一、什么是质数

质数（素数）指除了1和它本身外，不能被其他数整除的自然数。例如，2、3、5、7、11、13等都是质数。

二、方法一：暴力枚举法

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

这是最常见的判断质数的方法之一。从2开始循环遍历到n-1，如果n能被i整除，说明n不是质数。

虽然时间复杂度为O(n)，但是对于小范围的数，这种方法是可行的。

三、方法二：开方法

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

对于大范围的数，暴力枚举法的时间复杂度会很高，我们可以使用开方的方法来减少循环的次数。

一个数若有大于sqrt(n)的因子，那么一定有小于sqrt(n)的因子。因此，在循环条件中使用sqr = sqrt(n)，可以减少循环的次数。

四、方法三：质数判定定理

质数判定定理是一个重要的数学定理，它能够判断一个很大的数是否为质数。

根据费马小定理，如果p是质数，a是不是p的倍数，那么a的p-1次方除以p的余数一定是1。

long long pow_mod(long long a, long long b, long long p) {
    long long ans = 1 % p;
    for (; b; b >>= 1, a = (a * a) % p) {
        if (b & 1) {
            ans = (ans * a) % p;
        }
    }
    return ans;
}

bool isPrime(int n) {
    if (n == 2 || n == 3 || n == 5 || n == 7) {
        return true;
    }
    if (n == 1 || n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) {
        return false;
    }
    long long a[5] = {2, 3, 5, 7, 11};
    long long d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        ++s;
        d >>= 1;
    }
    for (int i = 0; i < 5; ++i) {
        if (n == a[i]) {
            return true;
        }
        long long t = pow_mod(a[i], d, n);
        if (t == 1) {
            continue;
        }
        for (int j = 0; j < s; ++j) {
            if (t == n - 1) {
                break;
            }
            t = (t * t) % n;
        }
        if (t != n - 1) {
            return false;
        }
    }
    return true;
}

这个算法的时间复杂度是O(klog³n)，其中k是测试次数，一般取15~20之间的数即可。

五、方法四：线性筛法

线性筛法不仅可以判断质数，还可以预处理出小于等于n的所有素数。

bool prime[N + 5];
int primes[N + 5], cnt = 0;

void getPrimes(int n) {
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (prime[i]) {
            primes[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * primes[j] <= n; ++j) {
            prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
}

该算法的时间复杂度为O(n)。

六、方法五：Miller-Rabin算法

Miller-Rabin算法是一种更加高效的质数判定算法，它可以在O(klog³n)的时间复杂度内完成，其中k是测试次数。

long long mul(long long a, long long b, long long mod) {
    long long ans = 0;
    for (; b; b >>= 1, a = (a + a) % mod) {
        if (b & 1) {
            ans = (ans + a) % mod;
        }
    }
    return ans;
}

long long pow_mod(long long a, long long b, long long mod) {
    long long ans = 1 % mod;
    a %= mod;
    for (; b; b >>= 1, a = mul(a, a, mod)) {
        if (b & 1) {
            ans = mul(ans, a, mod);
        }
    }
    return ans;
}

bool Miller_Rabin(long long n) {
    if (n < 2) {
        return false;
    }
    if (n == 2) {
        return true;
    }
    if (n % 2 == 0) {
        return false;
    }
    long long d = n - 1;
    while (d % 2 == 0) {
        d >>= 1;
    }
    for (int i = 0; i < 8; ++i) {
        long long a = rand() % (n - 2) + 2;
        long long x = pow_mod(a, d, n);
        long long y = 0;
        for (int j = 0; j < d; j++, x = y) {
            y = mul(x, x, n);
            if (y == 1 && x != 1 && x != n - 1) {
                return false;
            }
        }
        if (y != 1) {
            return false;
        }
    }
    return true;
}

这个算法利用费马小定理和欧拉定理，随机选择一个整数a，通过a^d % n与n来判断n是否为质数。

七、总结

本文介绍了5种判断质数的算法，分别是暴力枚举法、开方法、质数判定定理、线性筛法和Miller-Rabin算法。不同的算法适用于不同大小的数，选择合适的算法可以减少时间复杂度，提高程序效率。