#include <iostream>
#include <cmath>
using namespace std;

struct FactorList{
	int number;
	int factors[100];
	int left;
	int count = 0;
};

bool is_prime(int n){
		if (n <= 2){
			return n == 2; // 2 is prime, true.
		}
		if (n % 2 == 0){
			return false; // if even, false.
		}
		int sqrt_n = sqrt(n); // you only need to check up to the square root of the number, by Eratosthenes.
		for (int i = 3; i <= sqrt_n; i += 2){ // skipping evens.
			if (n % i == 0){
				return false;
			}
		}
		// if it got this far, it's prime.
		return true;
}

FactorList factor(FactorList f){
	int x,n;
	bool done = false;
	do{
		if(is_prime(f.number)){
			cout << f.number << " is prime, no other factors.\n";
			f.factors[f.count] = f.number;
			f.count++;
			done = true;
			return f;
		}else{
			n = f.left;
			for(x = 2;x <= n;x++){
				if(n % x == 0){
					if(is_prime(x) and x != n){
						// x is a prime factor
						cout << x << " is prime.\n";
						f.factors[f.count] = x;
						f.count++;
						f.left = n/x;
						cout << "terms left: " << f.left << endl;
						if(f.left == 1){
							done = true;
						}
						x = 1;
						n = f.left;
					}else{
						if(x == f.left and is_prime(f.left)){
							cout << f.left << " is prime, finished.\n";
							f.factors[f.count] = x;
							f.count++;
						}
						done = true;
					}
				}
			}
		}
	}while(not done);
	return f;
}

int main(){
	// find the prime factors by dividing the factors until there isn't anything composite left.
	FactorList f;
	bool done = false;
	int number;
	string temp;

	cout << "Enter the number to factor: ";
	cin >> number;

	f.number = number;
	f.left = f.number;
	f.count = 0;
	f = factor(f);

	cout << "Prime factors of " << f.number << ":"<< endl;
	for(int i=0; i < f.count; i++){
		cout << f.factors[i] << endl;
	}

	// print out the factors
	cout << f.count << " prime factors.\n";
	cout << "{";
	for(int i=0; i < f.count; i++){
		temp = to_string(f.factors[i]);
		cout << f.factors[i];
		if (i != f.count-1){ cout << ", "; }
	}
	cout << "}\n";
	return 0;
}