Question

In: Computer Science

Jojo just graduated and moved up to grade 4. Today is his first day in 4th...

Jojo just graduated and moved up to grade 4. Today is his first day in 4th grade. Unfortunately, the lessons are held online because of pandemic. So that the quality of learning remains good, Jojo’s teacher gives a hard task for 4th grader.

The first task is to find the prime factorization of a number. Prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. Prime factorization of a number is breaking a number down into the set of prime numbers which multiply together to result in the original number. Example below is the prime factorization of 1176.

. As a good friend of Jojo, help Jojo to solve the prime factorization task given by his teacher. Format Input There are T testcases. Each testcase contains an integer N which indicates the number to be factorized into prime factorization. Format Output Output T line with format “Case # X: ”, where X indicates the testcase number and then followed by the number prime factorization in ascending order of prime factors with the correct format.As a good friend of Jojo, help Jojo to solve the prime factorization task given by his teacher. Format Input There are T testcases. Each testcase contains an integer N which indicates the number to be factorized into prime factorization. Format Output Output T line with format “Case # X: ”, where X indicates the testcase number and then followed by the number prime factorization in ascending order of prime factors with the correct format.

Solutions

Expert Solution

How the algorithm works?

Step 1: We first find the number of 2s that divide the given number N.

  1. If N is divisible by 2, print a 2.
  2. Update N as N = N / 2.
  3. Repeat step 1 and step 2 till N remains divisible by 2.

Since 2 is the only even prime number. We now need to check only the odd prime numbers.

Step 2:
Now we start another loop from i = 3 till i <= square root of N.

Here we are making use of a special property of composite numbers:

Every Composite Number has at least one prime factor less than or equal to its Square Root.

Proof of this property:

  1. Let us suppose N is having two factors P and Q such that N = P*Q.
  2. If P and Q both are GREATER THAN N.
  3. Then P*Q > √N * √N, that is, P*Q > N
    But this is a contradiction to (1) which says P*Q = N.
    Therefore at least one prime factor of N is less than √N.


Step 3. In the loop that runs from i = 3 to i <= √N

  1. Check if i divides N. IF yes then print value of i.
  2. Divide N by i and update N. (This will reduce the number of i's in N).
  3. Update i = i+2
  4. Repeat these steps from 1 to 3 till N = 1 or N is a prime number.

HERE IS THE CODE:

Note: Since the programming language is not mentioned, I have coded the problem in C++.
But the logic remains same and can be achieved easily in other programming languages as well.

Program.cpp

#include <iostream>
#include <cmath>

using namespace std;

/*
    This function takes an a number N as input.
    It finds the prime factors of N and prints them in ascending order
*/
void primeFactors(int N)
{
    /* Find how many 2s divide N and print them */
    while (N % 2 == 0)
    {
        cout << 2 << " ";
        N = N / 2;
    }

    /*  
        Since 2 is the only even prime number so now we need to check only the ODD prime
        numbers and find how many times they divide N
    */

    // i starts at 3 (odd) and since i cannot be even therefore we update i = i+2
    for (int i = 3; i <= sqrt(N); i += 2)
    {
        //find how many i (3, 5, 7, ......so on) divide N and print them
        while (N % i == 0)
        {
            cout << i << " ";
            N = N / i;
        }
    }

    //handle those cases in which N is greater than 2
    if (N > 2)
    {
        cout << N;
    }
    printf("\n");
}

int main()
{
    int T; // Number of test cases
    int N; // The Number for which to find the prime factors

    // input the number of test cases
    cout << "Enter the number of test cases:\t";
    cin >> T;

    //input T numbers to find the prime factors for
    for (int i = 1; i <= T; i++)
    {
        //input a number
        cin >> N;
        cout << "Case # " << i << " : ";
        primeFactors(N); // print the prime factors
    }

    return 0;
}

Please refer to the screenshot of the code from editor to understand the indentation.



OUTPUT




Related Solutions

Jojo just graduated and moved up to grade 4. Today is his first day in 4th...
Jojo just graduated and moved up to grade 4. Today is his first day in 4th grade. Unfortunately, the lessons are held online because of pandemic. So that the quality of learning remains good, Jojo’s teacher gives a hard task for 4th grader. The first task is to find the prime factorization of a number. Prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. Prime factorization of a number is...
Take Three Jojo just graduated and moved up to grade 4. Today is his first day...
Take Three Jojo just graduated and moved up to grade 4. Today is his first day in 4th grade. Unfortunately, the lessons are held online because of pandemic. So that the quality of learning remains good, Jojo’s teacher gives a hard task for 4th grader. After the 4th graders finished their first task which is prime factorization. Jojo’s teacher set up a game for the stundets. The game is very simple. Given N colored balls, each student has to take...
C Programming Language Problem Title : 4th Grade Jojo just graduated and moved up to grade...
C Programming Language Problem Title : 4th Grade Jojo just graduated and moved up to grade 4. Today is his first day in 4th grade. Unfortunately, the lessons are held online because of pandemic. So that the quality of learning remains good, Jojo’s teacher gives a hard task for 4th grader. The first task is to find the prime factorization of a number. Prime number is a natural number greater than 1 that is not a product of two smaller...
C Programming Language Problem Title : Take Three Jojo just graduated and moved up to grade...
C Programming Language Problem Title : Take Three Jojo just graduated and moved up to grade 4. Today is his first day in 4th grade. Unfortunately, the lessons are held online because of the pandemic. So that the quality of learning remains good, Jojo's teacher gives a hard task for 4th grader. After the 4th graders finished their first task which is prime factorization. Jojo's teacher set up a game for the stundets. The game is very simple. Given N...
Burt is saving up for his retirement. Today is his 36th birthday. Burt first started saving...
Burt is saving up for his retirement. Today is his 36th birthday. Burt first started saving when he was 27 years old. On his 27th birthday, Burt made the first contribution to his retirement account when he deposited $2,000. Each year on his birthday, Burt has contributed another $2,000 to the account. The 10th (and last) of these contributions was made earlier today on his 36th birthday. The account has paid an effective annual rate of return of 5.4%. a)...
Burt Sbeez is saving up for his retirement. Today is his 40th birthday. Burt first started...
Burt Sbeez is saving up for his retirement. Today is his 40th birthday. Burt first started saving when he was just 25 years old. On his 25th birthday, Burt made the first contribution to his retirement account when he deposited $3,000. Each year on his birthday, Burt has contributed another $3,000 to the account. The 16th (and last) of these contributions is made today. The account has paid interest at the rate of 4.2% APR, compounded monthly. Burt wants to...
Grady​ Zebrowski, age​ 25, just graduated from​ college, accepted his first job with a ​$45 comma...
Grady​ Zebrowski, age​ 25, just graduated from​ college, accepted his first job with a ​$45 comma 000 ​salary, and is already looking forward to retirement in 40 years. He assumes a 3.5 percent inflation rate and plans to live in retirement for 20 years. He does not want to plan on any Social Security benefits. Assume Grady can earn a 6 percent rate of return on his investments prior to retirement and a 6 percent rate of return on his...
Grady​ Zebrowski, age​ 25, just graduated from​ college, accepted his first job with a $47,000 ​salary,...
Grady​ Zebrowski, age​ 25, just graduated from​ college, accepted his first job with a $47,000 ​salary, and is already looking forward to retirement in 40 years. He assumes a 2.1 percent inflation rate and plans to live in retirement for 20 years. He does not want to plan on any Social Security benefits. Assume Grady can earn a 9 percent rate of return on his investments prior to retirement and a 5 percent rate of return on his investments​ post-retirement...
Congratulations! You have just graduated from your University. Your first day on your new job involves...
Congratulations! You have just graduated from your University. Your first day on your new job involves a lot of paperwork including your decision to participate in the company 401K plan. First, should you participate? Second, describe the benefits of diversification if any including adding international stocks to your investment portfolio? You must include a full explanation to support your answer.
Assume that today is the first day of the month and that it is also your...
Assume that today is the first day of the month and that it is also your first day of retirement. You have saved for retirement over the years and have accumulated $310,000 in an investment account from which you plan to make monthly withdrawals during your retirement starting at the end of this month. Assuming you can earn annual returns of 6.4% in your investment account during your retirement years, how much money can you withdraw every month to make...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT