/*
 * Project name: Primes
 * Author: Isaac Good
 * Summary: This attempts to check is a given number is primes.
 * The number must be less than MSIZE.
 * Is the number is under 92500 the quick method is used (compute rough root, try dividing by all odd from 3 to rough root).
 * Otherwise an array of all primes up to MSIZE is built and checked.
 * The array can be built once and reused for many checks. That is the quickest method for many checks.
 * 
 * Project start:
 * July 16, ~10:30 am
 * Project end:
 * Jun 16, 11:55 am
 * 
 * This is under the MIT license like the rest of my software. See http://www.ecf.utoronto.ca/~goodi/html/software.html for the license.
 */

#include <stdio.h>
#include <time.h>

#define MSIZE 204800 //(1024 * 200)


int* findPrimes (void);
int isPrimeQuick (long);
long roughRoot (long);

// Get a long, and show if its prime.
int main (void) {
	long i;
	int *arr;

	scanf("%ld", &i);
	// Excedes max size?
	if (i <= MSIZE)
		printf("Try something lower, OK?\n");
	// Not too big to get rough root
	else if (i <= 92500)
		printf("Prime: %d\n", isPrimeQuick(i));
	// Construct an array
	else {
		arr = findPrimes();
		printf("Prime: %d\n", arr[i]);
	}
	
	return 0;
}

// Generate an array MSIZE long of all primes.
int* findPrimes () {
	int array[MSIZE];
	long i, j;
	clock_t start;
	
	start = clock();
	for (i = 3; i <= MSIZE; i += 2)
		array[i] = 1;
	
	for (i = 3; i <= MSIZE; i += 2)
		if (array[i]) {
			// printf("%d, ", i);
			for (j = i * 3; j <= MSIZE; j += i + i)
				array[j] = 0;
		}
	
	printf("Generating prime array up to %d took %ld ticks\n", MSIZE, clock() - start);
	return array;
}

// Quick check for prime. See if divisible by any odds up to its root.
int isPrimeQuick (long val) {
	long i, rroot;
	clock_t start;

	start = clock();

	if (val < 3)
		return 0;

	rroot = roughRoot(val);

	for (i = 3; i <= rroot; i +=2)
		if(!(val % i)) return 0;
	
	printf("Checking if %ld is prime took %ld ticks\n", val, clock() - start);

	return 1;
}

// Use the take divide by 2 method for finding the rough root. Never inaccurate to 1.
long roughRoot(long val) {
	long top, bottom, mid, midsqr;
	clock_t start;
	
	if(val > 92500) {
		printf("Can not compute root of %ld. Squaring %ld / 2 causes buffer overflow.\n", val, val);
		return 0;
	}
	
	start = clock();
	
	top = val;
	bottom = 0;
	
	if (val < 3) return 0;

	while ((top - bottom) != 1) {
		mid = (top + bottom) / 2;
		midsqr = mid * mid;
		
		printf("Top: %ld. Bottom: %d. Mid: %ld. Sqr: %ld\n", top, bottom, mid, midsqr);
		
		if (midsqr > val) top = mid;
		else if(midsqr < val) bottom = mid;
		else return mid;
	}
	
	printf("Generating root of %ld took %ld ticks\n", val, clock() - start);
	
	return bottom;
}