/**********************************************************************/
/* Matric Number: U051234A and U059876B                               */
/* Userid: u0501234 and u0509876                                      */
/* (For those doing pair programming, only ONE of you should submit   */
/*  your program. The other student should NOT submit.)               */
/* Lab: 2                                                             */
/* Lab Group Number: 99                                               */
/* Lab TA's Name: Who needs a lab TA when you're Bill Gates?          */
/* Lab Session Date: 4 October 2006                                   */
/* Lab Session Time: 0800 - 0945                                      */
/* Title: Fundamental Theorem of Arithmetic                           */
/* Purpose: To find the product of primes given a number.             */
/**********************************************************************/

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

int main(void)
{
    int n, prime = 0, first = 1, ceil_sqrt_n;
    printf("Enter a number: ");
    scanf("%d", &n);

    printf("The product of primes is ");
    ceil_sqrt_n = ceil(sqrt(n));

    do {
        if (prime != 2)
            prime += 2;
        else
            prime++;
        if (prime > ceil_sqrt_n)
            prime = n;
        while (n % prime == 0) {
            if (!first)
                printf(" x ");
            else
                first = 0;
            printf("%i", prime);
            n /= prime;
            ceil_sqrt_n = ceil(sqrt(n));
        }
    } while (n > 1);

    printf(".\n\n");

    return 0;
}