How To Find And Print All Prime Factors?

How To Find And Print All the Prime Factors?
How To Find And Print All the Prime Factors?

Introduction

Mathematics and Coding go hand in hand. There is no coding problem that cannot be solved by mathematical algorithms and similarly there is no mathematical problem that cannot be solved by coding constructs.

There are many fields of mathematics that use coding as a backbone to solve real-life problems like Numerical Analysis, Optimisation Techniques, and Statistics. Similar to these fields there is also an area of research that is served highly by coding constructs and that is Prime Numbers, Prims Algorithm, and Factors. Let’s learn more about them. 

What is Factorisation?

The word factorisation means finding factors of a natural number. A natural number ‘m’ is said to be a factor of a natural number ‘n’ when ‘n’ divided by ‘m’ leaves 0 as a remainder.  So, a natural number ‘n’ can be divisible by many natural numbers ‘m’. The process of finding all the factors of a natural number is called ‘factorisation’.


What is Prime Factorisation?

To understand Prime factorisation, we first need to understand what prime numbers are. A number ‘n’ is said to be a prime number if it has only two factors 1 and the number itself. 

Let us take an example of number 13:

  • A factor of a number can only be a number less than or equal to itself.
  • If we try to divide 13 with any number from 1, 2, 3…….. 13, the remainder would be 0 in only two cases when the divisor is 1 and 13.
  • So, here we can see that 13 has only two factors, hence it is a prime number. 

As prime numbers are not divisible by any other number except 1 and itself, so any number can be represented as a product of prime numbers. This process of representing a number as a product of prime numbers is called Prime factorisation and these factors are called Prime Factors.

For example, let’s take number 20 :

20 has a total of six factors 1, 2, 4, 5, 10, 20.

But each of these 6 factors can also be broken down into prime factors,
4 can be written as 22, 10 can be written as 25.

So, from above we can see that 20 in prime numbers can be written as 225.

blog banner 1

And hence prime factors of 20 are 2, 5.

Why Do We Need Prime Factorisation?

Prime factorisation is a very common concept in solving programming problems like:

  1. Find if the number is a perfect square/ perfect cube.
    • To solve this problem one can find Prime Factors of the number.
    • Then one can easily count the prime factors as Perfect Squares will have Prime Factors in pairs and Perfect Cubes will have prime factors in triplets.
  2. Encryption and Decryption.
    • Most encryption algorithms use a key that is a prime number. 
    • These prime numbers can also be a prime factor of the numerical value of the text.
  3. There can be only one unique set of prime factors for a number; no new set of prime factors can make the same number. This is called the Fundamental Theorem of Arithmetic. So, this can be used in solving some kind of real-life problems.
    • One such problem is finding the Factor Tree of a number. A factor tree is a Binary Search Tree or a Binary Tree in which leaf nodes of the tree have only prime numbers. This is a very common method used in dynamic programming problems.

Prime Factorisation Method 

The Prime factorisation Method is used to find the prime factors of a number. There are several ways to implement the prime factorisation method. Here we will discuss two different implementations of this method.

  • In this first method, we will use a smart approach. 
    • As we know that the prime numbers start from 2 and 2 is the only prime number that is even, so we will find the number of times the number divides by 2.
    • Then we will divide the number with all the odd numbers starting from 3 and less than the square root of the number.
    • We will run this loop till the square root of the number because the maximum prime factor of a number is the square root of that number.

Java Code For Prime Factorisation

//Importing Essential Libraries
import java.util.*;
import java.lang.*;
public class MyClass {
    
    //Function to find Prime Factors.
    public static void primeFact(int n)
    {
        //Print all the number 2 that divide the number
        while( n%2 == 0 )
        {
            System.out.print("2 ");
            n = n/2;
        }
        
        //Find all the next Prime Factors.
        for (int i = 3; i<=Math.sqrt(n); i=i+2)
        {
            while( n%i == 0)
            {
                System.out.print(i+" ");
                n=n/i;
            }
        }
	//Printing remainder if n>2 as it will be a prime number
        if(n>2)
        {
            System.out.print(n+" ");
        }
    }
    
    //Driver Function
    public static void main(String args[]) {
      Scanner in = new Scanner(System.in);
      System.out.println("Enter Number to find its prime factors.");
      
      //Take Input from the user.
      int num = in.nextInt();
      
      //Call primeFact function
      System.out.println("Prime Factors of "+num+" : ");
      primeFact(num);
    }
}

Output :
Enter Number to find its prime factors.
36
Prime Factors of 36 : 
2 2 3 3

Time Complexity : O(sqrt(n))
Space Complexity : O(1)
  • In this second method we will be finding the prime factors of a number but with a different approach where first we will find the prime numbers less than the square root of the number and then we will find the prime factors using these prime numbers only.

Implementation:

  • First, we will find the prime numbers less than the square root of the number using an algorithm known as the Sieve of Eratosthenes.
  • Sieve of Eratosthenes is a mathematical algorithm to find the prime numbers. In this algorithm, we maintain an array where we start from index 2 and keep on storing True or False in the index. 
  • If the number is a prime number then we will save true in that index else it will be false.
  • Then we will iterate over this sieve array to find the prime numbers and hence use these prime numbers to find the prime factors of the number.

Java Code for the above method:

//Importing Essential Libraries
import java.util.*;
import java.lang.*;
public class MyClass {
    
    static boolean[] sieve;
    
    public static void sieveFinder(int n)
    {
        //Declare Sieve Array
        sieve= new boolean[(int)Math.sqrt(n)+1];
        
        //Fill sieve array with true
        Arrays.fill(sieve,true);
        
        //Algo to find the prime numbers
        for(int i = 2;i<sieve.length;i++)
        {
            if(sieve[i]==true)
            {
                for(int j = i*2;j<sieve.length;j=j+i)
                {
                    sieve[j]=false;       
                }
            }
        }
    }
    
    //Function to find Prime Factors.
    public static void primeFact(int n)
    {
        //Calling sieveFinder to find Prime Numbers.
        sieveFinder(n);
        
        //Using Prime numbers to find Prime Factors
        for(int i = 2;i<sieve.length;i++)
        {
            if(sieve[i]==true)
            {
                while(n%i==0)
                {
                    System.out.print(i+" ");
                    n=n/i;
                }
            }
        }
        
        //Printing remainder if n>2 as it will be a prime number
        if(n>2)
        {
            System.out.print(n+" ");
        }
    }
    
    //Driver Function
    public static void main(String args[]) {
      Scanner in = new Scanner(System.in);
      System.out.println("Enter Number to find its prime factors.");
      
      //Take Input from the user.
      int num = in.nextInt();
      
      //Call primeFact function
      System.out.println("Prime Factors of "+num+" : ");
      primeFact(num);
    }
}

Output : 

Enter Number to find its prime factors.
22653
Prime Factors of 22653 : 
3 3 3 839

Time Complexity : O(n log(log(n))
Space Complexity : O(sqrt(n))

Frequently Asked Questions

How to find the prime factorisation of a large number in C?

The First approach will work fine for all the numbers that are in the range of the numbers that can be stored within the limits that the C compiler can support. Both the approaches will work fine but the first approach is far more efficient than the other.

And as we are talking about calculating prime factors for large numbers, we need to go with the more efficient approach.

How to find the prime factorisation of a large number in Python?

The above-mentioned approach will work fine for finding the prime factors of a large number in python. As told above, the time complexity of the efficient approach to finding the prime factorisation of a number is O(sqrt(n)), so this approach will work for large numbers.

How do you figure out if a number is prime or not?

It is very easy to determine if the number is prime or not, while calculating the prime factors of a number if there is only 1 prime factor and that too the number itself, then that number is a prime number.

How to find prime numbers between 1 and 100.

To find prime numbers between 1 and 100, simply implement a Sieve of Eratosthenes with ‘n’ as 100. Iterate over the sieve to find all the indexes where the value is True. Print all these indexes to get prime numbers between 1 and 100.

Key Takeaways

To conclude the entire discussion on Prime Factorisation, I will say that prime factors are a very essential part of programming. One should know how to find prime factors of a number as one can easily come across this problem during a Company Interview, College Exam, or a Coding Competition.

There are many problems that are built on prime factorisation methods but one needs to think out of the box to use this method in the right place to get accurate results.

By Sarthak Dhawan