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

int isprime(int);
void allprimes(int);
void allprimes2(int n);

int main(int argc, char **argv)
{
    /* 
       argc: number of arguments (including program name)
       argv: arguments as character strings
 */
    int i, n, t;
    if (argc != 3) {
	printf("Usage: isprime <n> <type>\n");
	return 1;
    }
    n = atoi(argv[1]);
    t = atoi(argv[2]);
    if (t == 1) allprimes(n);
    else allprimes2(n);
    return 0;
}


 /* function to detect if n is a prime */
int isprime(int n) {
    int m, i;
    m = (int) floor(sqrt(n));
    for (i = 2; i <= m; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

/* function to return all primes less than n */

void allprimes(int n) {
    int i;
    for (i = 2; i <= n; i++) {
        if (isprime(i)) {}
	    // printf("%d\n", i);
    }
    return;
}

/* more efficient version? */
void allprimes2(int n) {
    int i, j, k, m;
    int *x;
    /* create n-length logical vector of 1-s */
    x = (int *) malloc((n+1) * sizeof(int));
    x[0] = 0;
    x[1] = 0;
    for (i = 2; i <= n; i++) x[i] = 1;
    m = (int) floor(sqrt(n));
    for (i = 2; i <= m; i++) {
        if (x[i]) {
            k = n / i;
	    /* set all multiples of i to 0 */
            for (j = 2; j <= k; j++)
                x[j * i] = 0;
        }
    }
    for (i = 1; i <= n; i++)
	if (x[i]) {} // printf("%d\n", i);
    free(x);
    return;
}