Iterating primes using mpz_nextprime

Question

In C++, I want to print the first n prime numbers (for this example let's assume n=1000).

In order to do this, I've found mpz_nextprime from the GMP library.

I'd assume you use it like this

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

but this doesnt compile as mpz_nextprime takes two mpz_t arguments.

How can you use mpz_nextprime in this context?

Answer 1

The reason for mpz_nextprime using mpz_t instead of normal integer types like int or long is that after a certain point the prime numbers will be too large to be representable in a int or long.

Here's a snippet of code to print all up to the 1000th prime number:

#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;
    }
}

Note that this code will only work up to a certain prime number because in order to print it, we convert it to an unsigned int using mpz_get_ui here.

If you want to print larger prime numbers, use mpz_get_str (but don't forget to free() the string if you use NULL as first parameter).