/*
Programmer:	Greg Perkins
Program   :	factor2.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.  This is an improved version of
the original factoring program.  It has been modified to factor
very large numbers (up to and including the very largest value
possible for an unsigned long int.
*/

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

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

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

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

		if(is_prime(number))           /* if prime print PRIME message */
			printf("1 * %lu.  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() *************************/
unsigned long get_num()
{
	unsigned long num;
	printf("\nEnter the integer you want to factor.\n");
	printf("Enter 1 to quit.\n\n");
	scanf("%lu", &num);
	return(num);
}

/************************* is_prime() *************************/
int is_prime(unsigned long p)
{
	unsigned long curr_num = 2;          /* start divisor at 2 */ 
	double stop_num = sqrt((double) 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(unsigned long num)
{
	unsigned long 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("%lu * ", curr_factor);
			num /= curr_factor;		/* factor out curr_factor */
			if (is_prime(num))		/* check new num for primality */
			{
				printf("%lu.\n", num);
				break;
			}
		}
		else						/* get next prime to test */	
			curr_factor = next_prime(curr_factor);
	}

	return;
}

/************************* next_prime() *************************/
unsigned long next_prime(unsigned long 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);
}