How to resolve the algorithm Strong and weak primes step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Strong and weak primes step by step in the C programming language

Table of Contents

Problem Statement

Note that the definition for   strong primes   is different when used in the context of   cryptography.

Show all output here.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Strong and weak primes step by step in the C programming language

This C program finds and prints the first 36 strong and 37 weak prime numbers. Strong primes are prime numbers that are greater than the average of the previous and next prime numbers, while weak primes are those that are less than the average.

After including the necessary headers, the program defines an array of known prime numbers named PRIMES and calculates the length of this array. Function isPrime is defined to check whether a given integer n is prime. It starts with the assumption that n is prime, then checks for divisibility by primes in the PRIMES array until it finds a divisor or exceeds the square root of n (a common optimization for primality testing).

In the main function, memory is dynamically allocated for an array primePtr using calloc. The PRIMES array is copied into the beginning of primePtr. The program then loops through odd numbers starting from the last prime in PRIMES and checks each one for primality using the isPrime function. Newly found prime numbers are added to primePtr.

The program prints the first 36 strong and 37 weak primes found and counts how many of them are below 1,000,000 and 10,000,000. Finally, the program releases the allocated memory and exits.

Here is an example output:

First 36 strong primes:  13  19  23  31  37  43  47  59  61  67  71  79  83  89  97  101  103  107  109  127  137  139  151  157  163  173  179  181  191  193  211  223  227  229  239  251
There are 18 strong primes below 1,000,000
There are 35 strong primes below 10,000,000

First 37 weak primes:  3  5  11  17  29  31  41  43  47  53  59  67  73  79  89  97  103  109  127  137  139  157  163  179  181  193  199  211  227  233  239  251  257  263  269  271  277  283
There are 17 weak primes below 1,000,000
There are 36 weak primes below 10,000,000

Source code in the c programming language

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

const int PRIMES[] = {
    2, 3, 5, 7,
    11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
    101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
    307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523,
    541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
    773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
    1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217,
    1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
    1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663,
    1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907,
    1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141,
    2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383,
    2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659,
    2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
    2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163
};
#define PRIME_LENGTH (sizeof(PRIMES) / sizeof(int))

bool isPrime(int n) {
    int i;

    if (n < 2) {
        return false;
    }

    for (i = 0; i < PRIME_LENGTH; ++i) {
        if (n == PRIMES[i]) {
            return true;
        }
        if (n % PRIMES[i] == 0) {
            return false;
        }
        if (n < PRIMES[i] * PRIMES[i]) {
            break;
        }
    }

    return true;
}

int main() {
    const int MAX_LENGTH = 700000;
    int i, n, c1, c2;

    int *primePtr = calloc(MAX_LENGTH, sizeof(int));
    if (primePtr == 0) {
        return EXIT_FAILURE;
    }

    for (i = 0; i < PRIME_LENGTH; i++) {
        primePtr[i] = PRIMES[i];
    }

    i--;
    for (n = PRIMES[i] + 4; n < 10000100;) {
        if (isPrime(n)) {
            primePtr[i++] = n;
        }
        n += 2;

        if (isPrime(n)) {
            primePtr[i++] = n;
        }
        n += 4;

        if (i >= MAX_LENGTH) {
            printf("Allocate more memory.");
            return EXIT_FAILURE;
        }
    }

    /////////////////////////////////////////////////////////////
    printf("First 36 strong primes:");
    c1 = 0;
    c2 = 0;
    for (n = 0, i = 1; i < MAX_LENGTH - 1; i++) {
        if (2 * primePtr[i] > primePtr[i - 1] + primePtr[i + 1]) {
            if (n < 36) {
                printf("  %d", primePtr[i]);
                n++;
            }
            if (primePtr[i] < 1000000) {
                c1++;
                c2++;
            } else if (primePtr[i] < 10000000) {
                c2++;
            } else break;
        }
    }
    printf("\nThere are %d strong primes below 1,000,000", c1);
    printf("\nThere are %d strong primes below 10,000,000\n\n", c2);

    /////////////////////////////////////////////////////////////
    printf("First 37 weak primes:");
    c1 = 0;
    c2 = 0;
    for (n = 0, i = 1; i < MAX_LENGTH - 1; i++) {
        if (2 * primePtr[i] < primePtr[i - 1] + primePtr[i + 1]) {
            if (n < 37) {
                printf("  %d", primePtr[i]);
                n++;
            }
            if (primePtr[i] < 1000000) {
                c1++;
                c2++;
            } else if (primePtr[i] < 10000000) {
                c2++;
            } else break;
        }
    }
    printf("\nThere are %d weak primes below 1,000,000", c1);
    printf("\nThere are %d weak primes below 10,000,000\n\n", c2);

    free(primePtr);
    return EXIT_SUCCESS;
}

You may also check:How to resolve the algorithm Identity matrix step by step in the IS-BASIC programming language
You may also check:How to resolve the algorithm Sorting algorithms/Quicksort step by step in the RPL programming language
You may also check:How to resolve the algorithm Factors of an integer step by step in the F# programming language
You may also check:How to resolve the algorithm Magic squares of singly even order step by step in the Raku programming language
You may also check:How to resolve the algorithm Disarium numbers step by step in the Delphi programming language