Return to Answer

Based on @MOehm's second answer, I have managed to increase RANGE to 4 billion:

Based on @MOehm's second answer, I have managed to increase RANGE to 4 billion:

Based on @MOehm's second answer, I have managed to increase RANGE to 2 billion and beyond:

#include <limits.h>

// Defined by the user (must be less than 'UINT_MAX')
#define RANGE 2000000000

// The actual length required for the prime-sieve array
#define ARR_LEN (((RANGE-1)/(3*CHAR_BIT)+1))

// Assumes that all entries in 'sieve' are initialized to zero
void Init(char sieve[ARR_LEN]);

// Assumes that 'Init(sieve)' has been called and that '1 < n < RANGE'
int IsPrime(char sieve[ARR_LEN],unsigned int n);

#if RANGE >= UINT_MAX
    #error RANGE exceeds the limit
#endif

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

#define MAX_HIT_COUNT (RANGE/15) /* change the division factor if necessary */

typedef struct
{
    unsigned int n;
    unsigned int x;
}
hit;

char sieve[ARR_LEN]     = {0};
hit hits[MAX_HIT_COUNT] = {0};
unsigned int hit_count  =  0;

void Sprawl(unsigned long long n,unsigned long long sum,unsigned long long p)
{
    unsigned long long x = (unsigned long long)sqrt((double)sum);
    if (x*x == sum)
    {
        if (hit_count >= MAX_HIT_COUNT)
        {
            fprintf(stderr,"Hits overflow\n");
            exit(1);
        }
        hits[hit_count].n = (unsigned int)n;
        hits[hit_count].x = (unsigned int)x;
        hit_count++;
    }

    while (p < RANGE)
    {
        if (IsPrime(sieve,(unsigned int)p))
        {
            if (n*p >= RANGE)
                break;
            Sprawl(n*p,sum+p*p,p);
        }
        p++;
    }
}

Based on @MOehm's second answer, I have managed to increase RANGE to 4 billion:

#include <limits.h>

// Defined by the user (must be less than 'UINT_MAX')
#define RANGE 4000000000

// The actual length required for the prime-sieve array
#define ARR_LEN (((RANGE-1)/(3*CHAR_BIT)+1))

// Assumes that all entries in 'sieve' are initialized to zero
void Init(char sieve[ARR_LEN]);

// Assumes that 'Init(sieve)' has been called and that '1 < n < RANGE'
int IsPrime(char sieve[ARR_LEN],unsigned int n);

#if RANGE >= UINT_MAX
    #error RANGE exceeds the limit
#endif

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

#define MAX_HIT_COUNT (RANGE/20) /* change the division factor if necessary */

typedef struct
{
    unsigned int n;
    unsigned int x;
}
hit;

char sieve[ARR_LEN]     = {0};
hit hits[MAX_HIT_COUNT] = {0};
unsigned int hit_count  =  0;

void Sprawl(unsigned long long n,unsigned long long sum,unsigned long long p)
{
    unsigned long long x = (unsigned long long)sqrt((double)sum);
    if (x*x == sum)
    {
        if (hit_count >= MAX_HIT_COUNT)
        {
            fprintf(stderr,"Hits overflow\n");
            exit(1);
        }
        hits[hit_count].n = (unsigned int)n;
        hits[hit_count].x = (unsigned int)x;
        hit_count++;
    }

    while (p < RANGE)
    {
        if (IsPrime(sieve,(unsigned int)p))
        {
            if (n*p >= RANGE)
                break;
            Sprawl(n*p,sum+p*p,p);
        }
        p++;
    }
}

Based on @MOehm's second answer, I have managed to increase RANGE to 2 billion and more:

Based on @MOehm's second answer, I have managed to increase RANGE to 2 billion and beyond: