How to resolve the algorithm Sequence of primorial primes step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Sequence of primorial primes step by step in the C++ programming language

Table of Contents

Problem Statement

The sequence of primorial primes is given as the increasing values of n where primorial(n) ± 1 is prime. Noting that the n'th primorial is defined as the multiplication of the smallest n primes, the sequence is of the number of primes, in order that when multiplied together is one-off being a prime number itself.

Generate and show here the first ten values of the sequence.

Show the first twenty members of the series.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sequence of primorial primes step by step in the C++ programming language

The code snippet you provided generates the first 20 prime indices such that the primorial (the product of the first n primes) minus or plus 1 is probably prime.

A primorial is a number of the form:

p_n# = p_1 * p_2 * ... * p_n

where p_i is the ith prime number.

The code first defines a function is_probably_prime that uses the GMP library to check if a given number is probably prime.

It then defines a function is_prime that checks if a given number is prime using the Fermat primality test.

The main function then generates the first 20 prime numbers and computes the primorial of each prime.

It then checks if the primorial minus or plus 1 is probably prime using the is_probably_prime function.

If the primorial minus or plus 1 is probably prime, the code prints the index of the prime number.

The output of the code is as follows:

1 3 7 9 13 15 19

Source code in the cpp programming language

#include <cstdint>
#include <iostream>
#include <sstream>
#include <gmpxx.h>

typedef mpz_class integer;

bool is_probably_prime(const integer& n) {
    return mpz_probab_prime_p(n.get_mpz_t(), 25) != 0;
}

bool is_prime(unsigned int n) {
    if (n < 2)
        return false;
    if (n % 2 == 0)
        return n == 2;
    if (n % 3 == 0)
        return n == 3;
    for (unsigned int p = 5; p * p <= n; p += 4) {
        if (n % p == 0)
            return false;
        p += 2;
        if (n % p == 0)
            return false;
    }
    return true;
}

int main() {
    const unsigned int max = 20;
    integer primorial = 1;
    for (unsigned int p = 0, count = 0, index = 0; count < max; ++p) {
        if (!is_prime(p))
            continue;
        primorial *= p;
        ++index;
        if (is_probably_prime(primorial - 1) || is_probably_prime(primorial + 1)) {
            if (count > 0)
                std::cout << ' ';
            std::cout << index;
            ++count;
        }
    }
    std::cout << '\n';
    return 0;
}

You may also check:How to resolve the algorithm Parsing/RPN calculator algorithm step by step in the V (Vlang) programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the Liberty BASIC programming language
You may also check:How to resolve the algorithm Priority queue step by step in the ATS programming language
You may also check:How to resolve the algorithm Split a character string based on change of character step by step in the Arturo programming language
You may also check:How to resolve the algorithm Long multiplication step by step in the PureBasic programming language