Prime Factors Program in Java and Python

Question:

Algorithm:

Explanation:

Prime factorisation breaks a number into factors that are prime numbers. The program repeatedly divides the number by the smallest possible divisor.

The divisor starts from 2, the smallest prime number. If the current number is exactly divisible by the divisor, that divisor is printed as a prime factor.

After printing a factor, the number is divided by that factor. The same divisor is tested again because the same prime factor may occur more than once.

If the number is not divisible by the current divisor, the divisor is increased. This continues until the remaining number becomes 1, meaning all prime factors have been extracted.

When a divisor is successful, it is not increased immediately because the same prime factor may occur repeatedly. Only when division fails does the program move to the next possible divisor.

The divisor variable and the changing value of n work together. The loop repeatedly compares the remainder with zero, updates n after successful division, and increments the divisor only when the current divisor no longer divides n.

Prime factorisation breaks a number into factors that are prime. The program tests possible divisors starting from the smallest prime value. When a divisor divides the number exactly, it is printed or stored as a factor, and the number is divided by it. The same divisor is tested again because a prime factor may occur multiple times. Only when it no longer divides the number does the program move to the next possible divisor. This repeated reduction continues until the number is fully factorised.

Java Program:

/**
* The class PrimeFactors inputs a number and prints all its PrimeFactors
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
*/

import java.util.Scanner;
class PrimeFactors
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int n;
        System.out.print("Enter a Number : ");
        n=sc.nextInt();

        System.out.print("The Prime Factors of "+n+" are : ");

        int i=2;
        while(n>1)
        {
            if(n%i == 0)
            {
                System.out.print(i+" ");
                n=n/i;
            }
            else
            i++;
        }
    }
}

Equivalent Python Program:

# Read the number and keep any required copy for digit or divisor processing.
# Loops and conditions implement the number-property test step by step.
# Display the result according to the flag/counter/calculated value.

n = int(input("Enter a number: "))

print("The Prime Factors of", n, "are:", end=" ")

i = 2
while n > 1:
    if n % i == 0:
        print(i, end=" ")
        n = n // i
    else:
        i = i + 1

Output: