// Orozco, Joshua
// jeo575
// 16175
// EE312-Assignment 3
// Due: 2/25/11 Friday 11:59PM
// Purpose:
// 1. Gets input n from user and outputs the primes from 2 to n in rows and columns in
//    column-major order.
// 2. Outputs pairs consecutive primes if their difference is 4.
// 3. Outputs sums of 3 consecutive primes if the sum is prime also.

#include <stdio.h>
#include <math.h>
#include <limits.h>

//Initialize two functions

//1. Multiple max

int multiple_max(int c2)
{
    return c2*c2;
}

//2. Number of rows(n, columns)

int rows(int n, const int columns)
{    //Check how many rows(n, columns) are needed
    if (n % columns != 0)
    {
        return (n / columns) + 1;
    }
    else
    {
        return (n / columns);
    }
}

/*-------------------------------------------------------*/

int main()
{
    for(;;)
    {
        //Initialize input boundaries
        const int MAX_INPUT = 50000;

        //Initialize integers
        int input;
        int integers[MAX_INPUT];

        //Initialize counters
        int c1, c2, c3;

        //Initialize difference output
        int difference[MAX_INPUT];
        const int diff = 4;
        int p1, p2;

        //Initialize 3 consec. prime output
        int final_row;
        const int columns = 7;
        int consec[MAX_INPUT];
        int max;
        int check = 0;
        int a1, a2, a3;
        int j;

        //Initialize list of primes
        int primes[MAX_INPUT];
        int n = 0;

        //Initialize repeat
        char answer = 'N';

/*-------------------------------------------------------*/

        //Ask user for input
        printf("Input an integer from 2 to 50000 (inclusive): ");
        scanf("%d", &input);
        printf("\n");

        //Check if input is from 2 to 50000
        if (input >= MAX_INPUT && input <= 2)
        {
            do
            {
                printf("Bad input, please repeat: ");
                scanf("%d", &input);
                printf("\n");
            }
            while (input >= MAX_INPUT && input <= 2);
        }

//GOOOOOOOOOOOOOOOOOOOOD

        //Initialize array as prime = 0. Composite would = 1.
        for (c1 = 2; c1 <= input; c1++)
        {
                integers[c1]=0;
        }

        //0 and 1 are composite
        integers[0] = 1;
        integers[1] = 1;

        //Sieve, from 2 to i (user input)
        for (c2 = 2; multiple_max(c2) <= input; c2++)
        {
                if (integers[c2] == 0) //check if multiple is prime
                {
                        c1 = c2;
                        for (c3 = 2*c1; c3 <= input+1; c3 = c1+c3) //Go through multiples
                        {
                                integers[c3] = 1; //Mark as composite
                        }
                }
        }


        //Enter primes into a new array primes[n], n being the # of primes
        for (c1 = 0; c1 < input+1; c1++)
        {
                if (integers[c1] == 0)
                {
                        primes[n] = c1;
                        n++;
                }
        }

        printf("\n");

        //Output number of primes
        printf("There are this many primes: %d\n", n);

        //Output number of rows
        printf("There are this many rows needed: %d\n", rows(n, columns));

        //See how many columns are in the final row
        final_row = (n % columns);
        if (final_row == 0) //If no remainder, last row had all 8 columns
        {
                final_row = columns;
        }

        //Output number of primes in last row
        printf("There are this many primes in the last row: %d\n\n", final_row);

        //Output of primes in column-major order
        printf("Table of primes in column-major order\n");





   /*     for (input = 0; input < rows(n, columns); input++) //Loop to go through each row
        {
            int row_value = input;  //Value of the row starts with the row number
            int row_columns = columns; //Seven columns per row
            if (n%row_columns == 0)
            {
                if(input == rows(n, columns))  //Unless it's the last row
                row_columns = final_row;
            }
            else
            {
                if (input == rows(n, columns)-1) //Unless it's the last row
                row_columns = final_row;
            }
            for (j = 0; j<row_columns; j++) //Loop to go through the columns in that row
            {
                printf("%-5d ",primes[row_value]); //Output
                row_value = row_value+rows(n, columns); //Always increment the row value by the total row number
                if(j > final_row-1) //If the number is not in earlier column, subtract one (as less is added)
                {
                row_value--;
                }
            }
            printf("\n\n");
        }
*/

        //Output primes where difference between two consecutive primes is 4
        for (c1 = 0; c1 < n-1; c1++)
        {

            difference[c1] = primes[c1+1] - primes[c1]; //Difference
            p1 = primes[c1];   //Set values in array indexex to variables
            p2 = primes[c1+1];
            if (difference[c1] == diff)
            {
                printf("The pair of primes %d, %d has a difference of %d\n", p1, p2, diff); //Output
                c2++;
            }
        }

        //If no outputs for differences, say no pairs exist
        if (c2 == 0)
        {
            printf("There are no pairs of primes with a difference of %d\n", diff);
        }

        printf("\n");


        //Output primes where 3 consec. primes sum output is also prime
        for (c1 = 0; c1 < n-2; c1++)
        {

            consec[c1] = primes[c1] + primes[c1+1] + primes[c1+2];
            a1 = primes[c1];   //Set values in array indexex to variables
            a2 = primes[c1+1];
            a3 = primes[c1+2];
            max = consec[c1];
            check = 0; //Reset check to 0
            for (c2 = 2; multiple_max(c2) <= max; c2++) //Check whether max is prime or not
            {
                        if (max%c2 == 0) //If no remainder, means max is composite
                        {
                                check++; //Increment check, check != 0 means composite
                                break;   //If so, break for efficiency
                        }
            }

            if (check == 0) //If check = 0, max is prime. Output sum
            {
                        printf("%d + %d + %d = %d (which is a CPSP of order-3)\n", a1, a2, a3, max);
                        c3++;
            }
        }


        //If no outputs for differences, say no 3 consec. primes exist
        if (c3 == 0)
        {
            printf("There are does not exist a CPSP of order-3\n");
        }

        printf("\n");

        //Ask for input whether to repeat or not
        printf("Would you like to repeat? (Y/N): ");
        answer = getchar();
        scanf("%c", &answer);
        printf("\n");
        if (answer == 'N' || answer == 'n') //If enter 'N' or 'n', quit
        {
            printf("Goodbye");
            getchar();
            getchar();
            return 0;
        }
        else
        {
            printf("\n\n"); //If repeating, skip a few lines for organization/cleanliness
        }
    }
}