Question

Write a program which prompts the user for a positive integer, and then prints out the prime factorization of their response.

Do not import anything other than the Scanner.

One way you might go about this using nested loops:

• Start a "factor" variable at 2
• In a loop:
  • repeatedly print the current factor, and divide the user input by it, until the user input is no longer divisible by the factor
  • increment the factor

This plan is by no stretch of the imagination efficient, but it does the job.

HINT: You can the modulus operator % to determine if one integer is divisible by another. If a is divisible by b, then a % b (the remainder of division of a by b) has what value?

Answer 1

So based on the given problem and constraints I can think of 2 cases that we need to include in our solution that are when a number is a composite number and one where it is prime itself.

So for prime we can directly print the number out as it is the self prime factor of itself.

For composite number I have first print out all the times it is divisible by '2' by using a while loop and the '%' operator.

Then after the '2' to print out other prime factors of the number I have used another loop which starts with '3' and goes till the square root of the number left. By number left I mean to say that I have updated number itself everytime it is divisible by '2'. So the updated number after its done with all '2' factors will go through this loop and within this there is another loop which will print the other prime factors of the number and at the same time it will also update the number as done by the loop that checks '2' as the factor of the number.

Here is the Code for above Problem in Java:

Code:

import java.util.Scanner;
public class PrimeFactorisation {
public static void pFactors(int num)
{
while(num%2==0)
{
System.out.print(2+" ");
num/=2;
}

for(int i=3;i<=Math.sqrt(num);i+=2)
{
while(num%i==0)
{
System.out.print(i+" ");
num/=i;
}

}

if(num>2) // if number is prime then above steps won't work
System.out.print(num+" ");
}

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("Enter no.: ");
int num=sc.nextInt();

pFactors(num);
sc.close();
}
}

Some of the Outputs tested on the above code are:

For Composite Numbers:

For Prime Numbers:

For any doubt in Code or the approach to the problem do comment in the comments section.