Question

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.

Answer 1

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