/**
 * primes: a simple prime generator
 *
 * CS418, Spring 2004
 * Assignment # 1
 *
 */


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


#define NUMITERS 200
#define MAXSIZE 500000
#define MAXNUMPROCS 64

#define TRUE 1
#define FALSE 0

int lastPrime, count;      /* Last Prime and Number of Primes Found */
int size, numProcs;       
char *flags;               /* Array of primes (odd numbers only) 
                              i.e. flags[0] corresponds to 3
                              flags[1] corresponds to 5
                              flags[n] corresponds to 2*n+3
                              flags[i] is TRUE if i is a prime */

void primes(void);              /* procedure prototype */


/**
 * main routine:
 *
 */

int main(int argc, char *argv[])
{
    int i;

    /* Read command line arguments */
    if (argc != 3) {
        printf("Usage: %s numProcs numElts\n", argv[0]);
        exit(1);  
    }

    sscanf(argv[1], "%d", &numProcs);
    if (numProcs < 1 || numProcs > MAXNUMPROCS) {
        printf("Bad number of processors (%d)\n", numProcs);
        exit(1);  
    }

    sscanf(argv[2], "%d", &size);
    if (size < 0 || size > MAXSIZE) {
        printf("Bad size for array (%d)\n", size);
        exit(1);  
    }

    printf("  Prime Generator (%d elts, %d iterations on %d procs)\n", 
           size, NUMITERS, numProcs);

    flags = (char *) malloc(size * sizeof( char ) );
    if (!flags) {
        printf("\n   Could Not Allocate Memory for Array Size: %d\n",size);
        exit(1); 
    }

    primes();   /* Call our primes routine */

    free(flags);
    printf(" Number of primes = %d, last prime = %d\n", count, lastPrime);
}


/**
 * primes: prime number searching routine. 
 *
 *
 */
void primes()
{
    int i;
    int iter, prime;
    int div1, div2, rem;
    
    for (iter=0; iter < NUMITERS; ++iter)      
        /* This is just to make running time reasonable. 
           Don't parallelize this loop */
        {
            count = 0;
            lastPrime = 0;

            for (i=0; i < size; ++i) {    /* For every odd number */
                prime = 2 * i + 3;              
 
                /* Keep searching for divisor until rem == 0 (i.e. non prime),
                   or we've reached the sqrt of prime (when div1 > div2) */

                div1=1;
                do {                            
                    div1 += 2;            /* Divide by 3, 5, 7, ... */
                    div2 = prime / div1;  /* Find the dividend */
                    rem = prime % div1;   /* Find remainder */
                } while (rem != 0 && div1 <= div2); 

                if (rem != 0 || div1 == prime) {
                    /* prime is really a prime */

                    flags[i] = TRUE;
                    count++;                   
                    lastPrime = prime;
                } else {
                    /* prime is not a prime */
                    flags[i] = FALSE;         
                }
            }
        }
}