Assignment 1 – Factorials in terms of Prime Numbers

60-141 – Introduction to Programming II
The factorial of a number N (written N!) is defined as the product of all the integers from 1 to N. It is often defined recursively as follows:
0!=1 (By definition)
N!= N ×(N −1)!
[NOTE: Factorial of a negative number is undefined, and is not permitted.]
Factorials grow very rapidly — 5! = 120, 10! = 3,628,800. One way of specifying such large numbers is by specifying the number of times each prime number occurs in it. Thus 825 could be specified as (0 1 2 0 1) (or, (2,0) (3,1) (5,2) (7,0) (11,1)) meaning no twos, 1 three, 2 fives, no sevens and 1 eleven. For this assignment, we will follow the notation as: 825 = (2^0)*(3^1)*(5^2)*(7^0)*(11^1)
[NOTE: Although it is not required, students are advised to try to compute N! using simple integer multiplication in order to determine the largest N for which the computer does not produce an overflow. This optional exercise will underscore why this assignment is relevant in numeric computation.]
Your task is to:
Write a complete, well documented C program that will read in an integer number N (limited by 2 < N <100) and write out its factorial in terms of the numbers of its prime factors, using the output notation explained above.
Requirements and Hints:
1. You do not have to actually calculate the factorial of any number to solve this problem.
2. Given the first prime number 2, your program logic will:
a. Determine how many times this prime number will occur in N!.
b. Then the program will determine what is the next prime number, and go back to step a.
c. Steps a. and b. will continue until all the prime numbers < N are evaluated.
3. For example: 4! = 2X3X4, where the prime 2 occurs three times (2X4) = (2X2X2) = (2^3), and the prime 3 occurs only one time, (3^1). So 4! = (2^3)*(3^1). Likewise, 5! = (2^3)*(3^1)*(5^1).
4. Your program should implement at least the following 3 functions:
a. find_prime_count(), that will count the number of a given prime in N!.
b. find_next_prime(), that, given a prime number, will determine the next prime number.
c. is_prime(), that will determine whether a number is a prime number or not.
Input:
You have to use input redirection technique to enter inputs from a text file.
Example: a.out < input.txt
The input file will consist of a series of lines, each line containing a single integer N. The file will
be terminated by a line consisting of a single 0.
Output (you must follow the following format!):
Output will consist of a series of blocks of lines, one block for each line of the input. Each block
will start with the number N, right justified in a field of width 3, and the characters `!’, space, `=’
and 2 spaces.
This will be followed by a list of pairs of numbers in parenthesis, such as (x^y), separated by *,
where x is a prime number and y is the number of times the prime number x occurs in N!.
These should be right justified in variable width fields (shown below) and each line (except the
last of a block, which may be shorter) should contain 9 pairs of numbers. Any lines after the first
should be indented.
Follow the layout of the example shown below exactly.
Sample input file:
5
53
100
0
Sample output (you must follow the output format):
5! = (2^3)*(3^1)*(5^1)
53! = (2^49)*(3^23)*(5^12)*(7^8)*(11^4)*(13^4)*(17^3)*(19^2)*(23^2)
*(29^1)*(31^1)*(37^1)*(41^1)*(43^1)*(47^1)*(53^1)
100! = (2^97)*(3^48)*(5^24)*(7^16)*(11^9)*(13^7)*(17^5)*(19^5)*(23^4)
*(29^3)*(31^3)*(37^2)*(41^2)*(43^2)*(47^2)*(53^1)*(59^1)*(61^1)
*(67^1)*(71^1)*(73^1)*(79^1)*(83^1)*(89^1)*(97^1)
REQUIREMENTS:
– Write and document a complete C program that is capable of satisfying the requirements of this
assignment problem.

To create a script file (one that logs your compilation steps and your output in a text file):
1. script assign1.txt
2. cat assign1.c
3. cat input.txt
4. cc assign1.c
5. a.out < input.txt
6. ls -l
7. exit

Answer:

/*
Title: Assignment #1: Factorials in terms of prime numbers
Objective: This program will read in an integer number and write out its factorial in terms of
the numbers of its prime factors.
*/

//C-Preprocessor Directives

#include<stdio.h>

//Function Prototypes

int find_prime_count(int primeNumber, int num);
int find_next_prime(int num);
int is_prime(int num);

/*
Objective: This function is used to count number of times the prime number occurs in the entered number "num".
Input:prime number and number of occurrence of that number.
Output: Return number of times the prime number occurs.
*/

int find_prime_count(int primeNumber, int num){
    int counter = 0;
    while(num % primeNumber == 0){
        counter++;
        num /= primeNumber;
    }
    return counter;
}

/*
Objective: This function is used to find the next prime number.
Input:Non negative integer (num >0) .
Output: Return prime Number.
*/

int find_next_prime(int num){
    int nextPrime;
	//Choose the base case (num=1)
    if(num == 1) return num + 1;
	//Choose the base case (num=2)
	if(num == 2) return num + 1;
    //choose the next odd num
    if(num % 2 == 0) nextPrime += num ;
    else nextPrime = num + 2;
	//while loop to find next prime number and calling the"is_prime" function to check the next prime number
    while( !is_prime (nextPrime) )
        //Add 2 
        nextPrime += 2;
    return nextPrime;
}

/*
Objective: This function is used to check if the entered number "num" is prime number(return 1) or not prime number (return 0).
Input:Non negative integer (num >0) .
Output: Return 1 if num is prime number.
*/

int is_prime(int num){
	//Check if the passed number is 2
    if(num == 2 )return 1; 
	//Check if the passed number is 3
	if(num == 3 )return 1;
	//Check if we can divide the passed number by 2 with no remainder then it is not prime(return 0)
    if(num % 2 == 0) return 0; 
	//initializing the first prime and odd number after the 2
    int k = 3; 
	//Check if the number can be divided by 3 with no remainder
    while(num % k != 0){
		//The passed number to this function is prime number
        if(k * k > num) 
			//return "it is a prime number" and use the value for the next calculation
            return 1;
		//Add 2 and check if the next odd number is prime
        k +=2; 
    }
	//No more to check(return 0)
    return 0;
}


//Main function

int main(){

	//Declare variables
    int num,multiple;
	//Prompt the user to enter a number
    printf("\n\nPlease enter a number, or 0 to QUIT\n");
	//Store the value in variable num
	scanf("%d",&num);
	//Check if the entered number is positive between 2 to 100
	if (num>=2 && num<=100){
	
		//Main do while loop
		do{
		
			//Display the number "num" in a field of width 3 and the char "!" ,"space", "=" ,"2 spaces"
			printf("%3d! =  ", num);
			//start with the smallest prime Number which is "2"
			int primeNumber = 2, j = 0;

			/*While loop to check if 2 still less than or equal to the entered number
			and use the function "find_prime_count" to count how many times the prime number is repeating*/
			while(primeNumber <= num){
				//initializing "howMany"
				int howMany = 0;
				
				//for loop to find the prime count using "find_prime_count" function
				for(multiple = 1; multiple <= num; multiple++){
					//Check if the prime number is less than the multiple factor for a specific prime number
					if(primeNumber <= multiple)
						//Accumulator
						howMany += find_prime_count(primeNumber, multiple) ;
				}

				// Check if the number is not 2
				if (primeNumber != 2)
					//Display any prime Number other than 2 and how many times it appears with the specified format
					printf("*(%d^%d)", primeNumber, howMany);
				//if the number is 2
				else
					//Display num 2 and how many times it appears with the specified format
					printf("(%d^%d)", primeNumber, howMany);

				//Go to next prime Number by calling the "find_next_prime" function
				primeNumber = find_next_prime(primeNumber);
			    //increment j by 1(which is used to count how many prime numbers we have in one line)
				j++;
				//Go to next line after displaying 9 prime Numbers in one line
				if(j % 9 == 0)
					//after displaying 9 prime numbers in one line go to next line
					printf("\n       ");
			}//end while loop
			//Prompt the user to enter the next number
			printf("\n\nPlease enter the next number , or 0 to QUIT\n");
			//Accept the next number and store it in the variable num
			scanf("%d",&num);
	
		}while(num !=0);//End of do while loop
		//Prompt to the user if the entered number is 0 to quit the program
		printf("\nThank you for using this program. Please come back a gain \n");
	}
	//prompt to the user if the number entered less than 2 or greater than 100
	else {
		printf("\nThank you for using this program 🙂 \n");
	}
}