How to resolve the algorithm Wagstaff primes step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Wagstaff primes step by step in the C programming language

Table of Contents

Problem Statement

A Wagstaff prime is a prime number of the form (2^p + 1)/3 where the exponent p is an odd prime. (2^5 + 1)/3 = 11 is a Wagstaff prime because both 5 and 11 are primes. Find and show here the first 10 Wagstaff primes and their corresponding exponents p. Find and show here the exponents p corresponding to the next 14 Wagstaff primes (not the primes themselves) and any more that you have the patience for. When testing for primality, you may use a method which determines that a large number is probably prime with reasonable certainty. It can be shown (see talk page) that (2^p + 1)/3 is always integral if p is odd. So there's no need to check for that prior to checking for primality.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Wagstaff primes step by step in the C programming language

This C program finds the first 29 Wieferich primes below 2^32-1.

A Wieferich prime is a prime number p such that (2^p + 1)/3 is also prime.

The program uses the GNU Multiple Precision Arithmetic Library (GMP) to perform the necessary arithmetic operations.

Here's a breakdown of the code:

  • It includes the necessary headers: <stdio.h>, <string.h>, and <gmp.h>.
  • It defines a constant limit to specify the number of Wieferich primes to find.
  • It declares the main function.
  • It initializes two GMP integer variables p and w. p will be used to store prime numbers, and w will be used to calculate the Wieferich prime candidates.
  • It enters a while loop that continues until count reaches the specified limit.
  • Inside the loop, it finds the next prime number greater than the current value of p using mpz_nextprime.
  • It calculates w as (2^p + 1)/3 using GMP functions.
  • It checks if w is a prime number using mpz_probab_prime_p. If it is, the program has found a Wieferich prime.
  • It converts w to a string and formats it for printing.
  • It prints the found Wieferich prime and its length if it's longer than 34 digits.
  • It increments the count to keep track of the number of Wieferich primes found.
  • The loop continues until count reaches limit.

The program then returns 0 to indicate successful execution.

Source code in the c programming language

#include <stdio.h>
#include <string.h>
#include <gmp.h>

int main() {
    const int limit = 29;
    int count = 0;
    char tmp[40];
    mpz_t p, w;
    mpz_init_set_ui(p, 1);
    mpz_init(w);
    while (count < limit) {
       mpz_nextprime(p, p);
       mpz_set_ui(w, 1);
       unsigned long ulp = mpz_get_ui(p);
       mpz_mul_2exp(w, w, ulp);
       mpz_add_ui(w, w, 1);
       mpz_tdiv_q_ui(w, w, 3);
       if (mpz_probab_prime_p(w, 15) > 0) {
          ++count;
          char *ws = mpz_get_str(NULL, 10, w);
          size_t le = strlen(ws);
          if (le < 34) {
              strcpy(tmp, ws);
          } else {
              strncpy(tmp, ws, 15);
              strcpy(tmp + 15, "...");
              strncpy(tmp + 18, ws + le - 15, 16);
          }
          printf("%5lu: %s", ulp, tmp);
          if (le >=34) printf( " (%ld digits)", le);
          printf("\n");
       }
    }
    return 0;
}


  

You may also check:How to resolve the algorithm Bulls and cows step by step in the Python programming language
You may also check:How to resolve the algorithm Burrows–Wheeler transform step by step in the BQN programming language
You may also check:How to resolve the algorithm Averages/Root mean square step by step in the 11l programming language
You may also check:How to resolve the algorithm Optional parameters step by step in the R programming language
You may also check:How to resolve the algorithm Integer sequence step by step in the Applesoft BASIC programming language