Saturday 20 May 2017

C Program - Simple Prime Number Calculation

This can be optimised at least a bit - can you do this??

/* C Program to Calculate Prime Numbers
   A.D. Johnson, 10.95
   Used for speed comparison with a Interpreted Basic program.

    We determine Prime Numbers by taking the next number in a sequence
    then dividing it in turn by all the previous prime numbers we have
    so far calculated (each prime number is stored in an array as we go
    along). The process gets longer and longer every time we have a new
    prime number.
*/
#include <stdio.h>
#include <time.h>

#define MAX_PRIMES_FOUND 100000

/* Declare an array to store the Prime numbers we find.*/
long primes[MAX_PRIMES_FOUND];

/* Start of program. */
int main ()
{
   /* Set up the variables. */
   long no_primes = 0, divided;
   long number,j;
   time_t start_time;


   printf ("Prime Numbers Calculation Program. Calculating... ");

   /* Note start time. */
   start_time = time (NULL);

   /* Calculate Primes in the range 2 to 2500000 */
   for (number = 2; (number <= 2500000) && (no_primes < MAX_PRIMES_FOUND); number++)
   {
      /* Use this as a flag to show whether we have divided wholly. */
          divided = 1;

      /* Divide our current number by each of the primes we have found so far. */
          for (j = 0; (j < no_primes) ; j++)
          {
         /* The % is the "MOD" operation. */
                 divided = number % primes[j];

         /* If we had a whole division, break out of the loop. */
                 if (!divided)
                    break;
          }
      /* If we had a whole division, "divided" is 0 and hence
         prime number not found. */
          if (divided)
          {
         /* Store the prime number we found. */
                 primes[j] = number;
                 //printf ("%ld\n",j);

         /* Increase the number of primes found. */
                 no_primes++;
          }
   }

   /* Report. */
   printf ("\nFinished in %2.0f seconds!\n",difftime (time(NULL), start_time));
   printf ("Found %ld Prime numbers... Press a key to list them!\n", no_primes);

   /* Wait for a key to be pressed. */
   getchar();

   /* Show the prime numbers found. */
   for (j=0; j < no_primes; j++)
   {
      printf ("%8ld", primes[j]);
   }

   /* Wait for eenter to be pressed. */
   getchar();
   return 0;
}
Old "cal" C program.

/******************************************************************************/
/*         Calendar Program - 16.1.89 - A. Johnson                         /
/*   This program "Cal" when run from CLI will generate Calendars for any     /
/* Month or year. It emulates the UNIX command "cal" (surprise, surprise)     /
/* in this respect. Uses "Zeller's date congruence" function to calculate     /
/* days of week for first day of month.                                                 /
/******************************************************************************/

/******************************************************************************

    Operation:

    When compiled and run, the user can type "cal 1992" for a calendar listing
    of 1992, or "cal 3 1992" for a calendar of March 1992.

    The program first gets the command line arguments, then calls
    a funtion to initialize a data array. This function calls the
    "zeller_day_no" function to get the day number (0 to 6) for the first
    day of each month. This is then used as a starting point for the calendar
    for that month.

    When run, re-direction can be used to put the output of this program to
    the printer, or to a file.

*****************************************************************************/

/* Include 2 of the standard C header files for the functions / definitions
    we will be using. */
#include <stdio.h>
#include <stdlib.h>



/******************     Data for building up calendar  *******************/

    /* We will print the calendar out in a 3 x 4 grid of months. */
    /* We will print out 3 months at "a time". /
    /* A month can spread across 6 weeks!         /
    /* Declare an array to hold 3 months' worth of days. */
    int    month_array[3][7][6] = {0};

    /* Declare an array to hold the days in each month. */
    int    days_in_month[12] = {
                                              31,  /* Jan */
                                              28,  /* Feb */
                                              31,  /* Mar */
                                              30,  /* Apr */
                                              31,  /* May */
                                              30,  /* Jun */
                                              31,  /* Jul */
                                              31,  /* Aug */
                                              30,  /* Sep */
                                              31,  /* Oct */
                                              30,  /* Nov */
                                              31     /* Dec */
                                      };

    /* Declare some working variables. */
    int    working_month, working_year, leap_day;

    /* Declare an array of strings for the days of the week */
    char day_string[7]={
                                    "Sun", "Mon",    "Tue", "Wed",
                                    "Thu", "Fri",    "Sat"
                                };

    /* Declare an array of strings for the months of the year. */
    char months[12]=    {
                                    "Jan", "Feb", "Mar", "Apr", "May", "Jun",
                                    "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"
                                };

/*****************************************************************************
* Function:       zeller_day_no                                                           
* Description:   Gives the number of the day of the week for the given date.
* Parameters:      int day - date, int month - month no, int year - AD year  
* Returns:          day of week as an int in range  0 to 6, 0 being Sunday.  
******************************************************************************/
int zeller_day_no (int day, int month, int year)
{
    int temp, yr1, yr2;

    /* Now do Zeller's jiggery pokery with the numbers to work out a
        day number from the day, month and year parameters. */
    if (month < 3)
    {
        month += 10;
        year -= 1;
    }
    else month -=2;

    yr1 = year / 100;
    yr2 = year % 100;
    temp = (26 * month - 1)/10;

    return ((day + temp + yr2 + yr2/4 + yr1/4 - 2 * yr1 +49)%7);
}


/*****************************************************************************
* Function:       do_months                                                                
* Description:   Fills up the "month array" with day values.                   
* Parameters:      int - month number, int - year number int - no. of months
* Returns:          nothing                                                                   
******************************************************************************/
void do_months (int month, int year, int no_of_months)
{
    int temp_day, day_no, week_number,i;


    /* Do for the specified number of months. */
    for (i=0; i < no_of_months; i++)
    {
        /* Get the number of the day for the first day of the month. */
        day_no = zeller_day_no (1, month+i+1, year);

        /* Initialize array at beginning and end to stop overlap problems later. */
        for (temp_day = 0; temp_day <= 6; temp_day++)
        {
          /* Use multiple assignment. */
          month_array[i][temp_day][0] = month_array[i][temp_day][4]=
          month_array[i][temp_day][5] = 0;
        }

        /* Initialise a "week in month" counting variable. */
        week_number = 0;

        /* Now just put the day numbers in the month array, picking out the
            number of days in the month from "days_in_month". */
        for (temp_day = 1; temp_day <= (days_in_month[month+i]); temp_day++)
        {
            /* Initialise the array element. */
            month_array[i][day_no][week_number] = temp_day;

            /* Increment the day number. */
            day_no ++;

            /* Now we do "MOD 7" to make the day number always go round from
                0 to 6 */
            day_no %= 7;

            /* Check if "day no" wrapped round - if so, we increment the week
                counter. */
            if (day_no == 0)
            {
                /* Move to the next week. */
                week_number++;
            }
        }
    }
}

/*****************************************************************************
* Function:       print_months                                                            
* Description:   Prints out the specified number of months using the data in *
*                      "month array".                                                           
* Parameters:      int - month number, int - no. of months                        
* Returns:          nothing                                                                   
******************************************************************************/
void print_months(int month, int no_of_months)
{
      int weekday, week_number, month_no;

      /* Print out the month titles. */
      for (month_no = month; month_no < month + no_of_months; month_no++)
      {
          /* Print the months name first. */
          printf ("%14s           ", months[month_no]);
      }

      /* When we are just printing a single month, show the year also. */
      if (no_of_months == 1)
      {
          printf ("\n\n%14d", working_year);
      }
      /* Print a carriage return or 2. */
      printf ("\n\n");

      /* Print out a given day of the week for each month e.g. print all
          the Sundays, then all the Mondays etc. */
      /* Do each weekday... */
      for (weekday = 0; weekday <= 6; weekday++)  /* Start at Sunday */
      {
          /* ... for each month... */
          for (month_no = 0; month_no < no_of_months; month_no++)
          {
                printf ("  %s", day_string[weekday]);      /* Print the day.      /

                /* ... do each week. */
                for (week_number = 0; week_number <= 5; week_number++)
                {
                    /* We are only going to print non-zero elements of the array. */
                    if (month_array[month_no][weekday][week_number])
                    {
                         printf ("%3d", month_array[month_no][weekday][week_number]);
                    }
                    else
                    {
                         printf ("   ");             /* ... print spaces instead. */
                    }
                }
                printf ("  ");             /* End of month - space out. */
          }
          printf ("\n");                    /* End of months - next line.*/
      }
      printf("\n\n");                     /* End of months' block.  /
}


/******************************************************************************/
/* The Main program!                                                                          /
/******************************************************************************/
/* The arguments to main are used to access what was typed on the command line. */
void main (int argument_count, char **argument_table_ptr)
{
    int temp_month, end_month, no_of_months;


    printf ("\n");

    /************************************************************************
  The following works out whether we will print out a single month from *
  the year (2 arguments) or the whole year (1 argument passed).         
  The months are then printed out in blocks.                                  
 ************************************************************************/

    /* Check the number of arguments which were typed on the command line. */
    if ((argument_count==1) || (argument_count > 3))
    {
         printf ("CAL V1.1 Calendar Generator\n\n");
         printf ("Usage:\tCal [month no.] Year \te.g.\n");
         printf ("\tCal 1992 \t\tfor a calendar of 1992.\n");
         printf ("\tCal 1 1993 \t\tfor a calendar of January 1993.\n");
    }
    else
    {
        /* When the argument count is 2, we want to do a Whole Year! */
        if (argument_count == 2)
        {
          /* Get the year as typed on the command line. */
          /* This is a string so we have to convert it to an integer using
              "atoi". */
          working_year = atoi (*++argument_table_ptr);
          /* Set the last month we wish to do. */
          end_month = 12;
          /* We are going to do it in 3 month blocks. */
          no_of_months = 3;
          /* Start in month 1 - January. */
          working_month = 1;
          /* Print a prompt. */
          printf ("%30sCalendar for  %d\n\n"," ",working_year);
        }
        else /* A month and year has been specified. */
        {
            /* Get the month from the command line and convert it to "int". */
            working_month = atoi (*++argument_table_ptr);
            /* Get the year from the command line and convert it to "int". */
            working_year  = atoi (*++argument_table_ptr);
            /* We are only going to do this month. */
            end_month = working_month;
            /* We do just one month. */
            no_of_months = 1;             /* Only 1 month to do!     /
        }


        /* Now we are going to check a valid month number has been typed. */
        if ((working_month < 1) || (working_month > 12))
        {
            printf ("\n\n***Invalid Month number!***\n\n");
        }
        else
        {
            /* Have we got a Leap year situation? (This is the full formula.) */
            if (((working_year % 4) == 0) && ((working_year % 100) != 0) ||
                ((working_year % 400) == 0))
            {
                 /* Re-initialize February in "days in month" to have 29 days! */
                 days_in_month[1] = 29;
            }
        }

        /* Do calendar for the specified number of months.        /
        /* This will print out the months in blocks of 3 or 1. */
        for (temp_month = working_month; temp_month <= end_month; temp_month += no_of_months)
        {
             /* Now do the business... */
             /* Initialise the months array. */
             do_months (temp_month - 1, working_year, no_of_months);
             /* Print out the data. */
             print_months(temp_month - 1, no_of_months);
        }
    }
}