/*
Programmer:	Greg Perkins
Program   :	factor.c
Class     :    CS 73
Due       :    10 February 1998

This program will factor any positive integer greater than 1 as a
product of prime factors.  If the original number entered by the
user is already prime, the program will display "1 * number" and
indicate that the number is prime.
*/

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

/* FUNCTION PROTOTYPES */
int get_num();
int is_prime(int p);
void factor(int num);
int next_prime(int p);

/* FUNCTION DEFINITIONS */
/***********************    main()    **************************/
int main()
{
	int number = get_num();             /* get number to factor */

	while(number > 1)                   /* 2 is the smallest prime */
	{
		printf("%d = ", number);

		if(is_prime(number))           /* if prime print PRIME message */
			printf("1 * %d.  PRIME\n", number);
		else
			factor(number);           /* if not prime factor number */

		number = get_num();            /* get number to factor */
	}

	printf("Goodbye...\n");

	return (0);
}

/************************* get_num() *************************/
int get_num()
{
	int num;
	printf("\nEnter the integer you want to factor.\n");
	printf("Enter 1 to quit.\n\n");
	scanf("%d", &num);
	return(num);
}

/************************* is_prime() *************************/
int is_prime(int p)
{
	int curr_num = 2;                  /* start divisor at 2 */ 
	float stop_num = sqrt((float) p);  /* no divisor > sqrt of number needed */

	while(curr_num <= stop_num)
	{
		if ((p % curr_num) == 0)      /* not prime if evenly divisible */
			return (0);
		else
			curr_num++;              /* increment divisor */
	}

	return(1);                         /* not evenly divisible, return prime */
}

/************************* factor() *************************/
void factor(int num)
{
	int curr_factor = 2;			/* start factoring at 2 */

	while (num >= 2)				/* factor in terms of primes only */
	{
		if((num % curr_factor) == 0)	/* found a prime factor */
		{
			printf("%d * ", curr_factor);
			num /= curr_factor;		/* factor out curr_factor */
			if (is_prime(num))		/* check new num for primality */
			{
				printf("%d.\n", num);
				break;
			}
		}
		else						/* get next prime to test */	
			curr_factor = next_prime(curr_factor);
	}

	return;
}

/************************* next_prime() *************************/
int next_prime(int p)
{
	int prime_found = 0;

	while (!prime_found)
	{
		if (p <= 1)			/* if low number comes in, then */
			p = 2;			/* next prime is always 2 (first prime */
		else
			if ((p % 2) == 0)	/* no even primes */
				p++;			/* make the number odd before test */
			else
				p += 2;		/* get next odd number to test */

		prime_found = is_prime(p);
	} 
	
	return (p);
}