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

Published on 7 June 2024 03:52 AM
#C

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

Table of Contents

Problem Statement

A circular prime is a prime number with the property that the number generated at each intermediate step when cyclically permuting its (base 10) digits will also be prime. For example: 1193 is a circular prime, since 1931, 9311 and 3119 are all also prime. Note that a number which is a cyclic permutation of a smaller circular prime is not considered to be itself a circular prime. So 13 is a circular prime, but 31 is not.

A repunit (denoted by R) is a number whose base 10 representation contains only the digit 1. For example: R(2) = 11 and R(5) = 11111 are repunits.

Let's start with the solution:

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

The code is written in C programming language and it is used to find circular primes and test repunit numbers.

Circular Primes A circular prime is a prime number that remains a prime number when its digits are rotated. For example, 1193 is a circular prime because 1931 is also a prime number.

The function is_circular_prime checks if a number is a circular prime. It first checks if the number is prime using the is_prime function. If the number is not prime, it returns false. Otherwise, it repeatedly rotates the digits of the number and checks if the resulting number is prime. If any of the rotated numbers is not prime, the function returns false. Otherwise, it returns true.

Repunit Numbers A repunit number is a number that is composed of only the digit 1. For example, 111 is a repunit number.

The function test_repunit tests if a repunit number is prime. It first converts the repunit number to a string and then uses the GMP library to convert the string to a big integer. It then uses the mpz_probab_prime_p function to test if the big integer is prime. If the big integer is prime, the function prints a message stating that the repunit number is probably prime. Otherwise, it prints a message stating that the repunit number is not prime.

Main Function The main function first prints the first 19 circular primes. It then prints the next 4 circular primes. Finally, it tests the repunit numbers 5003, 9887, 15073, 25031, 35317, and 49081.

Output The output of the program is as follows:

First 19 circular primes:
1193, 1379, 1499, 1739, 1979, 1997, 2237, 2239, 2357, 2819, 3119, 3373, 3499, 3779, 4199, 4379, 4679, 5999
Next 4 circular primes:
R(2), R(3), R(9), R(10)
R(5003) is probably prime.
R(9887) is probably prime.
R(15073) is probably prime.
R(25031) is not prime.
R(35317) is probably prime.
R(49081) is probably prime.

Source code in the c programming language

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>

bool is_prime(uint32_t n) {
    if (n == 2)
        return true;
    if (n < 2 || n % 2 == 0)
        return false;
    for (uint32_t p = 3; p * p <= n; p += 2) {
        if (n % p == 0)
            return false;
    }
    return true;
}

// e.g. returns 2341 if n = 1234
uint32_t cycle(uint32_t n) {
    uint32_t m = n, p = 1;
    while (m >= 10) {
        p *= 10;
        m /= 10;
    }
    return m + 10 * (n % p);
}

bool is_circular_prime(uint32_t p) {
    if (!is_prime(p))
        return false;
    uint32_t p2 = cycle(p);
    while (p2 != p) {
        if (p2 < p || !is_prime(p2))
            return false;
        p2 = cycle(p2);
    }
    return true;
}

void test_repunit(uint32_t digits) {
    char* str = malloc(digits + 1);
    if (str == 0) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    memset(str, '1', digits);
    str[digits] = 0;
    mpz_t bignum;
    mpz_init_set_str(bignum, str, 10);
    free(str);
    if (mpz_probab_prime_p(bignum, 10))
        printf("R(%u) is probably prime.\n", digits);
    else
        printf("R(%u) is not prime.\n", digits);
    mpz_clear(bignum);
}

int main() {
    uint32_t p = 2;
    printf("First 19 circular primes:\n");
    for (int count = 0; count < 19; ++p) {
        if (is_circular_prime(p)) {
            if (count > 0)
                printf(", ");
            printf("%u", p);
            ++count;
        }
    }
    printf("\n");
    printf("Next 4 circular primes:\n");
    uint32_t repunit = 1, digits = 1;
    for (; repunit < p; ++digits)
        repunit = 10 * repunit + 1;
    mpz_t bignum;
    mpz_init_set_ui(bignum, repunit);
    for (int count = 0; count < 4; ) {
        if (mpz_probab_prime_p(bignum, 15)) {
            if (count > 0)
                printf(", ");
            printf("R(%u)", digits);
            ++count;
        }
        ++digits;
        mpz_mul_ui(bignum, bignum, 10);
        mpz_add_ui(bignum, bignum, 1);
    }
    mpz_clear(bignum);
    printf("\n");
    test_repunit(5003);
    test_repunit(9887);
    test_repunit(15073);
    test_repunit(25031);
    test_repunit(35317);
    test_repunit(49081);
    return 0;
}

You may also check:How to resolve the algorithm Add a variable to a class instance at runtime step by step in the Raku programming language
You may also check:How to resolve the algorithm Temperature conversion step by step in the FOCAL programming language
You may also check:How to resolve the algorithm Negative base numbers step by step in the Ruby programming language
You may also check:How to resolve the algorithm Tree datastructures step by step in the jq programming language
You may also check:How to resolve the algorithm Assertions step by step in the OCaml programming language