/*
 * 
 * Even number squared plus one.
 *
 * An even number squared plus one is either prime or can be divided
 * by a previous (2n)^2+1
 */

#include <stdint.h>

typedef struct prime0_item_s {
    struct prime0_item_s *next;
    uint64_t item;
} prime0_item;

void prime0_init(prime0_item **list, uint32_t *counter);
uint64_t prime0_iterate(prime0_item *list, uint32_t *counter);

/* SPLIT HERE */

#include <stdlib.h>

void prime0_init(prime0_item **list, uint32_t *counter)
{
    *list = malloc(sizeof(prime0_item));
    (*list)->next = NULL;
    (*list)->item = 5;
    *counter = 2;
}

uint64_t prime0_iterate(prime0_item *list, uint32_t *counter)
{
    register uint64_t number, d;
    uint64_t stop;
    char insert_here;
    prime0_item *item, *next;
    /* Step to the next even number */
    *counter += 2;
    /* MUST expand the counter before calculating the next candidate. */
    stop = (uint64_t) *counter;
    number = stop * stop + 1;
    /* Begin factorization */
    for (item = list; item; item = item->next)
    {
        d = item->item;
        if (d >= stop || 1 == number)
            break;
        while (0 == number % d)
            number /= d;
    }
    /* If number isn't one, it must be a new prime. */
    if (1 != number)
    {
        for (item = list; item; item=item->next)
        {
            /* Criteria for correct placement. */
            if (item->next)
                insert_here = item->next->item > number;
            else
                insert_here = 1;
            if (insert_here)
            {
                /* Insert the new prime */
                next = item->next;
                item->next = malloc(sizeof(prime0_item));
                item->next->item = number;
                item->next->next = next;
                break;
            }
        }
    }
    return number;
}


/* SPLIT HERE */

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

int main(int argc, char *argv[])
{
    uint32_t counter, stop;
    prime0_item *list, *item;
    char *ign;
    
    if (argc != 2)
    {
        fputs(
            "Usage: prime0 stop-number\n"
            "\n"
            "This program will print a list of primes that are factors\n"
            "to squared even numbers plus one.  stop-number will be the\n"
            "highest number that will be squared.\n"
            "",
            stderr
        );
        return 1;
    }
    
    stop = strtoul(argv[1], &ign, 0);
    
    prime0_init(&list, &counter);
    
    while (counter <= stop)
        prime0_iterate(list, &counter);
    
    for (item = list; item; item = item->next)
        printf("%llu\n", item->item);
}