#include <iostream> // basic i/o
#include <iomanip> // output formatting
#include <cmath> // math functions
using namespace std;

int main(){

// === PHASE 1 ===
	int num = 2;
	int primes[1000];
	int i = 0;
	cout << "1 is neither prime nor composite\n";
	while(num <= 400){
		if(num % 2 == 0 and num != 2){
			cout << num <<  " is divisible by 2\n";
		}else if(num % 3 == 0 and num != 3){
			cout << num <<  " is divisible by 3\n";
		}else if(num % 5 == 0 and num != 5){
			cout << num <<  " is divisible by 5\n";
		}else if(num % 7 == 0 and num != 7){
			cout << num <<  " is divisible by 7\n";
		}else if(num % 11 == 0 and num != 11){
			cout << num <<  " is divisible by 11\n";
		}else if(num % 13 == 0 and num != 13){
			cout << num << " is divisible by 13\n";
		}else if(num % 17 == 0 and num != 17){
			cout << num << " is divisible by 17\n";
		}else if(num % 19 == 0 and num != 19){
			cout << num << " is divisible by 19\n";
		}else{
			cout << num << " is a PRIME CANDIDATE\n";
			// if the number is not composite, it must be prime
			// add it to the list of primes
			primes[i] = num;
			i++;
		}
		num++;
	} // end PHASE 1

	// output the list of primes
	for(int n=0; n<x; n++){
		cout << big_primes[n];
		if(n+1 != x){ 
			cout << ","; 
		}else{
			cout << endl;
		}
	}

// now we have all the primes under 400.
// === PHASE 2 ===
	int big_primes[20000];
	int x = 0;
	//there are i primes in the original list.
	cout << "************\nSEED PRIMES:\n";
	while(x < i){
		big_primes[x] = primes[x];
		cout << big_primes[x] << endl;
		x++;
	}
	cout << "************\n";
	num = 401; // pick up where we left off.
	// count is the index in the list of seed primes.
	int count;
	bool possible_prime;
	while(num <= 160000){
		// each number starts out a possible prime.
		cout << "Checking: " << num << ".\n"; 
		possible_prime = true;
		// restart from the first prime factor.
		count = 0;
		// don't exceed the number of seed primes.
		while(count < i){
			// if you can divide the number by the current seed prime
			if(num % primes[count] == 0){
				// the number is composite.
				cout << num << " is divisible by " << primes[count] << ".\n";
				// advance to the next number.
				possible_prime = false;
				break;
			}
			count++;
		}
		// if it's still possible and we got through the list of prime factors to check, it's prime.
		if(possible_prime){
			cout << num << " is PRIME.\n";
			big_primes[x] = num;
			// there's one more prime in the array.
			x++;
		}

		// move to the next number.
		num++;
	}

	cout << "\nDONE.\n";
	cout << x << " primes found.\n";

	// output the list of primes
	for(int n=0; n<x; n++){
		cout << big_primes[n];
		if(n+1 != x){ 
			cout << ","; 
		}else{
			cout << endl;
		}
	}

	return 0;
}