使用 mpz_nextprime 迭代素数

Question

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

为了做到这一点，我从 GMP 库中找到了 mpz_nextprime。

我假设你是这样使用它的

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() 字符串）。

使用 mpz_nextprime 迭代素数

Iterating primes using mpz_nextprime

c++

gmp