c++ - 使用 mpz_nextprime 迭代素数

Question

在 C++ 中，我想打印第一个 n 个素数(对于这个例子，我们假设 n=1000)。

为了做到这一点，我找到了 mpz_nextprime来自 GMP 库。

我假设你是这样使用它的

int n = 2;
for(int i = 0; i < 1000; i++) {
    n = mpz_nextprime(n);
    cout << n << endl;
}

但这不会编译为 mpz_nextprime 需要两个 mpz_t 参数。

如何在这种情况下使用 mpz_nextprime？

Answer 1

mpz_nextprime 使用 mpz_t 而不是像 int 或 long 这样的普通整数类型的原因是在某些时候，质数将太大而无法用 int 或 long 表示。

这是打印所有直到第 1000 个素数的代码片段:

#include <gmp.h>

int main() {
    mpz_t n;
    mpz_init(n);
    mpz_set_ui(n, 2);
    for (size_t i = 0; i < 1000; i++) { // first 1000 primes
        mpz_nextprime(n, n);
        cout << "The " << (i + 1) << "th " << " prime is " << mpz_get_ui(n) << endl;
    }
}

请注意，此代码仅适用于特定质数，因为为了打印它，我们在此处使用 mpz_get_ui 将其转换为无符号整数。

如果你想打印更大的素数，使用mpz_get_str(但如果你使用NULL，不要忘记free()字符串> 作为第一个参数)。