Starting from:
$30
COMP1410-Assignment 1 Factorials in terms of Prime Numbers Solved
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,you 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. T
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 problem.
-
The question requires use of I/O redirection
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,you 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. T
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 problem.
-
The question requires use of I/O redirection
1 file (1.5KB)
