How to resolve the algorithm Ulam spiral (for primes) step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Ulam spiral (for primes) step by step in the C programming language

Table of Contents

Problem Statement

An Ulam spiral (of primes) is a method of visualizing primes when expressed in a (normally counter-clockwise) outward spiral (usually starting at 1),   constructed on a square grid, starting at the "center". An Ulam spiral is also known as a   prime spiral. The first grid (green) is shown with sequential integers,   starting at   1. In an Ulam spiral of primes, only the primes are shown (usually indicated by some glyph such as a dot or asterisk),   and all non-primes as shown as a blank   (or some other whitespace). Of course, the grid and border are not to be displayed (but they are displayed here when using these Wiki HTML tables). Normally, the spiral starts in the "center",   and the   2nd   number is to the viewer's right and the number spiral starts from there in a counter-clockwise direction. There are other geometric shapes that are used as well, including clock-wise spirals. Also, some spirals (for the   2nd   number)   is viewed upwards from the   1st   number instead of to the right, but that is just a matter of orientation. Sometimes, the starting number can be specified to show more visual striking patterns (of prime densities). [A larger than necessary grid (numbers wise) is shown here to illustrate the pattern of numbers on the diagonals   (which may be used by the method to orientate the direction of spiral-construction algorithm within the example computer programs)]. Then, in the next phase in the transformation of the Ulam prime spiral,   the non-primes are translated to blanks. In the orange grid below,   the primes are left intact,   and all non-primes are changed to blanks.
Then, in the final transformation of the Ulam spiral (the yellow grid),   translate the primes to a glyph such as a   •   or some other suitable glyph.

The Ulam spiral becomes more visually obvious as the grid increases in size.

For any sized   N × N   grid,   construct and show an Ulam spiral (counter-clockwise) of primes starting at some specified initial number   (the default would be 1),   with some suitably   dotty   (glyph) representation to indicate primes,   and the absence of dots to indicate non-primes.
You should demonstrate the generator by showing at Ulam prime spiral large enough to (almost) fill your terminal screen.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Ulam spiral (for primes) step by step in the C programming language

The code you provided is an implementation of the Ulam spiral in C. The Ulam spiral is a two-dimensional arrangement of prime numbers that is generated by walking in a spiral pattern and marking each prime number as you go.

The code first defines a type called bitsieve to represent a bitset of prime numbers. It then defines a function called sieve_check that checks if a given number is prime by looking it up in the bitset.

Next, the code defines a function called sieve that generates a bitset of prime numbers up to a given limit. It does this by iterating over all the odd numbers up to the limit and marking off all the multiples of each prime number.

Once the bitset of prime numbers has been generated, the code defines a function called ulam_get_map that maps a given coordinate in the spiral to a prime number. It does this by using a formula that takes into account the size of the spiral and the position of the coordinate.

Finally, the code defines a function called output_ulam_spiral that prints out the Ulam spiral for a given size. It does this by iterating over all the coordinates in the spiral and printing out the prime number that corresponds to each coordinate.

The main function of the program calls the output_ulam_spiral function for a given size and then prints out the result.

The second code you provided is also an implementation of the Ulam spiral, but this time in C++. It uses a similar algorithm to the first code, but it uses a different data structure to represent the bitset of prime numbers.

The main function of the program calls the isprime function to check if a given number is prime and the spiral function to map a given coordinate in the spiral to a prime number. It then iterates over all the coordinates in the spiral and prints out the prime number that corresponds to each coordinate.

Source code in the c programming language

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

typedef uint32_t bitsieve;

unsigned sieve_check(bitsieve *b, const unsigned v)
{
    if ((v != 2 && !(v & 1)) || (v < 2))
        return 0;
    else
        return !(b[v >> 6] & (1 << (v >> 1 & 31)));
}

bitsieve* sieve(const unsigned v)
{
    unsigned i, j;
    bitsieve *b = calloc((v >> 6) + 1, sizeof(uint32_t));

    for (i = 3; i <= sqrt(v); i += 2)
        if (!(b[i >> 6] & (1 << (i >> 1 & 31))))
            for (j = i*i; j < v; j += (i << 1))
                b[j >> 6] |= (1 << (j >> 1 & 31));

    return b;
}

#define max(x,y) ((x) > (y) ? (x) : (y))

/* This mapping taken from python solution */
int ulam_get_map(int x, int y, int n)
{
    x -= (n - 1) / 2;
    y -= n / 2;

    int mx = abs(x), my = abs(y);
    int l = 2 * max(mx, my);
    int d = y >= x ? l * 3 + x + y : l - x - y;

    return pow(l - 1, 2) + d;
}

/* Passing a value of 0 as glyph will print numbers */
void output_ulam_spiral(int n, const char glyph)
{
    /* An even side length does not make sense, use greatest odd value < n */
    n -= n % 2 == 0 ? 1 : 0;

    const char *spaces = ".................";
    int mwidth = log10(n * n) + 1;

    bitsieve *b = sieve(n * n + 1);
    int x, y;

    for (x = 0; x < n; ++x) {
        for (y = 0; y < n; ++y) {
            int z = ulam_get_map(y, x, n);

            if (glyph == 0) {
                if (sieve_check(b, z))
                    printf("%*d ", mwidth, z);
                else
                    printf("%.*s ", mwidth, spaces);
            }
            else {
                printf("%c", sieve_check(b, z) ? glyph : spaces[0]);
            }
        }
        printf("\n");
    }

    free(b);
}

int main(int argc, char *argv[])
{
    const int n = argc < 2 ? 9 : atoi(argv[1]);

    output_ulam_spiral(n, 0);
    printf("\n");

    output_ulam_spiral(n, '#');
    printf("\n");

    return 0;
}


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

int isprime(int n)
{
	int p;
	for (p = 2; p*p <= n; p++)
		if (n%p == 0) return 0;
	return n > 2;
}

int spiral(int w, int h, int x, int y)
{
	return y ? w + spiral(h - 1, w, y - 1, w - x - 1) : x;
}

int main(int c, char **v)
{
	int i, j, w = 50, h = 50, s = 1;
	if (c > 1 && (w = atoi(v[1])) <= 0) w = 50;
	if (c > 2 && (h = atoi(v[2])) <= 0) h = w;
	if (c > 3 && (s = atoi(v[3])) <= 0) s = 1;

	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++)
			putchar(isprime(w*h + s - 1 - spiral(w, h, j, i))[" #"]);
		putchar('\n');
	}
	return 0;
}

You may also check:How to resolve the algorithm Sorting algorithms/Stooge sort step by step in the C programming language
You may also check:How to resolve the algorithm Deepcopy step by step in the C programming language
You may also check:How to resolve the algorithm Doubly-linked list/Traversal step by step in the C programming language
You may also check:How to resolve the algorithm Hello world/Web server step by step in the C programming language
You may also check:How to resolve the algorithm Variable size/Get step by step in the C programming language