Problem 2 (Stacks): Consider the fundamental theorem of arithmetic, which is stated as follows: Every positive integer greater than 1 can be written uniquely as a prime or as the product of two or more primes, where the prim
Problem 2 (Stacks): Consider the fundamental theorem of arithmetic, which is stated as follows:
Every positive integer greater than 1 can be written uniquely as a prime or as the product of two
or more primes, where the prime factors are written in order of nondecreasing size. We want to
use a stack to read a number and print all of its prime divisors in descending order. For example,
with the integer 2100, the output should be:
7 5 5 3 2 2
1. Write an
than 1, and generates its prime factorization according to the above-mentioned theorem.
[Hint: The smallest divisor greater than 1 of any integer is guaranteed to be a prime.]
2. Propose a stack class to accommodate this prime decomposition. It should have at least
two member functions: One to compute the prime factorization of an integer, and one to
print all corresponding prime divisors in descending order.
3. Give an implementation of all member functions defined in the above stack class.
1. First declare a variable - iterate=2 and input a variable - number (to find its prime factors.)
2. Run a While loop-1 to check if the number is not equal to 1
3. Inside the loop there is a conditional statement if (number %iterate ==0)
4. If the condition satisfies print the variable- iterate ,which are the prime factors
5. Then another while loop-2 is run with condition (number % iterate==0)
Inside this while loop -update number=number / iterate , till the condition satisfies
6. While loop-2 fails we increment the iterating variable by 1 =iterate++
7. Line number 2 follows again, While loop -1 checks the condition
Pseudo-Code
number , iterate=2 ;
Input (number)
while (number!=1)
{
if (number % iterate==0)
{
Print (Iterate)
}
while (number % iterate==0)
{
number = number / iterate;
}
Iterate ++;
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps